目录

一、线性表

一、顺序表

1、静态分配

2、动态分配

 3、插入、删除、查找实现

 二、单链表

1、按位插入 

一、线性表

定义：具有相同数据类型的n（n >= 0）个数据元素的有限序列

分类：顺序表和链表
           顺序表（其实就是数组）里面元素的地址是连续的；
           链表里面节点的地址不是连续的，是通过指针连起来的；

主要操作

InitList(&L):        初始化操作，建立一个空的线性表；
Length(L):           求表长，返回线性表 L 的长度，即 L 中数据元素的个数；
Empty(L):            若线性表为空，返回true，否则返回false；
ClearList(*L):       线性表清空；
GetElem(L,i,*e):     按位查找，将线性表L中第i个位置元素返回给e；
LocateElem(L,e):     按值查找，在线性表L中查找与给定值e相等的元素；
ListInsert(*L,i,e):  在线性表的第i个位置插入元素e；
ListDelete(*L,i,*e): 删除线性表L中的第i个元素，并用e返回其值；
PrintList(L):        打印线性表；

一、顺序表

定义：一般使用数组实现，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定连续的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中，数组大小有两种方式指定，一是静态分配，二是动态扩展。

typedef 用法：typedef  类型  别名;        即给选定的某个类型设置一个别名

1、静态分配

#include 
#include
#define maxSize 10    //表长度的初始化定义

typedef int ElemType;
typedef struct {
	ElemType data[maxSize];    //用静态的“数组”存放数据元素
	int length;    //顺序表的当前长度
}SqlList;    //顺序表的定义类型

//初始化
void InitList(SqlList& L, int len) {
    //不初始化会有脏数据
	for(int i=0;i 
2、动态分配 
malloc函数返回一个指针，需要强制转型为定义的数据元素类型指针，malloc函数的参数指明要分配多大的连续内存空间，当不需要时可以使用 free函数释放掉内存空间，使用 malloc 函数需要 使用 #include
 
#include 
#include
#define maxSize 10    //表长度的初始化定义

typedef int ElemType;
typedef struct {
	ElemType* data;
	int length;
}SqlList;

//初始化
void InitList(SqlList& L, int len) {
	L.data = (ElemType*)malloc(sizeof(ElemType) * (maxSize + len));
    for(int i=0;i 
 
 
 3、插入、删除、查找实现 
 
#include 
#include
#define maxSize 10

typedef int ElemType;
typedef struct {
	ElemType* data;
	int length;
}SqlList;

//初始化
void InitList(SqlList& L, int len) {
	L.data = (ElemType*)malloc(sizeof(ElemType) * (maxSize + len));
	for (int i = 0;i < maxSize;i++) {
		L.data[i] = 0;	//将所有数据元素设置为默认初始值
	}
	L.length = 0;	//顺序表初始长度为0
}

//添加数据
bool InsertList(SqlList& L, int i, ElemType e) {
	if (i < 1 || i > maxSize || L.length > maxSize)
		return false;
	for (int j = L.length; j >= i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i-1] = e;
	L.length++;
	return true;
}

bool DelList(SqlList& L, int i, ElemType& e) {
	//同上先判断要删除的元素的位置是否合法
	if (i < 1 || i > L.length) {
		return false;
	}
	//判断顺序表中有没有元素
	if (L.length == 0) {
		return false;
	}

	e = L.data[i - 1];      //获取顺序表中对应的元素,赋值给e

	//移动顺序表中元素
//    for (int j = L.length; j >= i; j--) {
//        L.data[j] = L.data[j - 1];
//    }
	for (int j = i; j < L.length; ++j) {        //删除元素,是向前覆盖的,和插入元素相反
		L.data[j - 1] = L.data[j];
	}
	L.length--;     //删除一个元素后,顺序表长度减1；
	return true;
}
//按值查找
int LocateElem(SqlList L, ElemType e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i+1;
	}
	return 0;	//退出循环，声明查找随便
}

//遍历输出
void PrintList(SqlList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%d n", L.data[i]);
	}
}

void main () {
	SqlList L;
	int len = 0;
	ElemType del;
	InitList(L, len);
	if (InsertList(L, 1, 1) && InsertList(L, 2, 2) && InsertList(L, 3, 3) && InsertList(L, 4, 4)) {
		printf("====插入成功====n");
		printf("插入后顺序表中的元素为:n");
		PrintList(L);
	}
	else{
		printf("添加失败 n");
	}

	printf("查找值的位置在 %d n", LocateElem(L, 2));

	if (DelList(L, 1, del)) {
		printf("删除成功n");
		printf("删除元素的值为%dn", del);
		PrintList(L);
	}else
		printf("删除失败 n");
}
 
 
运行实现
 
  
 
 
 
 二、单链表 
 
1、按位插入 
带头结点
 
 
 
 
//按位插入
//带头结点
bool ListInsertHead(LinkList& L, int i, ElemType e) {
    if (i < 1)
        return false;

    LNode* p;       //指针指向当前扫描到的结点
    int j = 0;      //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存在数据）

    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }

    if (p == NULL)  //i值不合法
        return false;

    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
 
不带头结点
 
 
//不带头结点
bool ListInsertNonHead(LinkList& L, int i, ElemType e) {
    if (i < 1)
        return false;
    if (i == 1) {   //插入第一个结点的操作和其他结点操作不同
        LNode* s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;    
        L = s;      //头指针指向新节点
        return true;
    }

    LNode* p;       //指针指向当前扫描到的结点
    int j = 1;      //当前p指向的是第几个结点
    p = L;          //p第1个结点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL)  //i值不合法
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}