顺序表

静态顺序表 

    #include
    #define MaxSize 10//定义最大长度
    typedef struct {
        int data[MaxSize];//定义静态数组
        int length;//顺序表当前长度
    }SqList;
    

void InitList(SqList& L) {
    for (int i = 0;i < MaxSize;i++) {
        L.data[i] = 0;//所以数据初始值为0
    }
    L.length = 0;//顺序表初始长度为0
}
int main() {
    SqList L;//声明顺序表
    InitList(L);//调用函数，初始化顺序表
    return 0;
}

动态分配 

    #include
    #include
    #define InitSize 10;
    //定义顺序表
    typedef struct {
        int *data;     //动态数组指针
        int MaxSize;   //当前最大容量
        int length;    //当前长度
    }SeqList;


void InitList(SeqList &L) {
    L.data = (int*)malloc((L.MaxSize) * sizeof(int));//开辟容量为MaxSize的空间
    L.length = 0;//初始化长度
    L.MaxSize = InitSize;//最大容量为10
}
//增加容量
void IncreseSize(SeqList& L, int len) {
    int* p = L.data;//将数组首项地址赋予*p
    L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));//增加len*sizeof(int)长度空间
    for (int i = 0;i < L.length;i++) {
        L.data[i] = p[i];//将L.data数组中的值转移到新的空间
    }
    L.MaxSize = L.MaxSize + len;//最大长度增加
    free(p);//释放旧存储空间
}
int main() {
    SeqList L;
    InitList(L);
    for (int i = 0;i < L.MaxSize;i++) {
        L.data[i] = 1;
    }
    IncreseSize(L, 5);//5=len
    return 0;
}

插入 

    #include
    #define MaxSize 10//定义最大长度
    typedef struct {
        int data[MaxSize];//定义静态数组
        int length;//顺序表当前长度
    }SqList;


bool ListInsert(SqList &L, int i, int e) {
    if (i<1 || i>L.length)//判断插入位置是否合法
        return false;
    if (L.length >= MaxSize)//同上
        return false;
    for (int j = L.length;j >= i;j--)
        L.data[j] = L.data[j - 1];//将i后元素后移一位
    L.data[i - 1] = e;//插入e
    L.length++;//使顺序表当前长度加一
    return true;
}
void InitList(SqList& L) {
    for (int i = 0;i < MaxSize;i++) {
        L.data[i] = 0;//所以数据初始值为0
    }
    L.length = 0;//顺序表初始长度为0
}
int main() {
    SqList L;
    InitList(L);
    //插入元素
    ListInsert(L, 3, 3);//在第三个位置插入3
    return 0;
}

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
基本结构
	typedef struct LNode {
		int data;
		struct LNode* next; //指向下一个结构体。
	}LNode, * LinkList;
	
初始化
	void InitList(LinkList &L){
		L = (LNode *)malloc(sizeof(LinkList));申请头指针的内存
		L->next = NULL; 将头指针置空
	}

尾插法建立单链表
	LinkList TailInsert(LinkList &L){
		InitList(L);
		LNode *s,*r=L;
		int x;
		cin>>x;
		while(x!=9999){
			s = (LNode *)malloc(sizeof(LNode));
			s->data = x;
			r->next = s;
			r = s;
			cin>>x;
		}
		r->next = NULL;
		return L;
	}

头插法建立单链表
	LinkList HeadInsert(LinkList &L){
		InitList(L); //初始化
		int x;
		cin>>x;
		while(x!=9999){ 
			LNode *s = (LNode *)malloc(sizeof(LNode));
			s->data = x;
			s->next = L->next;
			L->next = s;
			cin>>x;
		}
		return L;
	}
	
遍历单链表
	void PrintList(LinkList L) {
		LNode* p = L->next;
		while (p) { //当p指向NULL跳出循环。
			cout << p->data << " ";
			p = p->next;
		}
		cout << endl;
	}	

求链表长度
	int Length(LinkList L){
		LNode *p = L->next;
		int len = 0;
		while(p){
			len++; //每读取一个节点len自增。
			p = p->next;
		}
		return len;
	}	

按值查找
	LNode *LocateElem(LinkList L, int x){
		LNode *p = L->next;
		while(p && p->data != x){
			p = p->next;
		}
		return p;
	}	

按位查找
	LNode *GetElem(LinkList L, int i){
		int j=1;
		LNode *p = L->next;
		if(i==0)return L;
		if(i<1)return NULL;
		while(p && j<i){
			p = p->next;
			j++;
		}
		return p; // 如果i大于表长，p=NULL，将返回p
	}

插入
	void Insert(LinkList &L, int i, int x){
		LNode *p = GetElem(L,i-1);
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		s->next = p->next;
		p->next = s;
	}

删除
	void Delete(LinkList &L, int i){
		if(i<1 || i>Length(L))
			cout<<"delete failed: index is wrong."<<endl;
			return;
		LNode *p = GetElem(L,i-1);
		LNode *q = p->next;
		p->next = q->next;
		free(q);
	}

判空
bool Empty(LinkList L){
    if(L->next == NULL){
        cout<<"L is null"<<endl;
        return true;
    }
	else{
        cout <<"L is not null"<<endl;
        return false;
    }
}