文章目录

2.1抽象运算（算法2.1） 2.2顺序表存储的Ｃ语言实现创建一个空的顺序表（算法2.3）用类C语言实现顺序表的插入删除按值查找（顺序查找） 2.32.3.1.单链表单链表的C语言实现用类C语言实现单链表上的查询(查找第i个元素)：单链表上的插入运算(第i个元素位置上插入新的结点)单链表上的删除运算(把第i个元素删除)用类C语言实现表头插入算法：用类C语言实现两个有序单链表的合并 2.3.2.循环单链表和双向链表双向链表的C语言描述

---

2.1

抽象运算（算法2.1）

例2-1 利用两个线性表LA和LB分别表示集合A和B，求一个新的集合A=A∪B。

算法思路：集合中的元素间是松散的关系，只需将在线性表LB中而不在LA中的数据元素追加到LA的尾部即可。

void union(List &La, List Lb) { // 获取线性表的长度 La_len = Length(La); Lb_len = Length(Lb); // 遍历Lb中的每个元素 for(i = 1;i <= Lb_len; i++) { // 获取Lb线性表中的第j个元素，存储到e中 GetElem(Lb, i, e); // 判断在La线性表中根据 equal比较 是否存在e if (!LocatElem(La, e, equal)) // 不存在就尾插插入e到La中 InsertElem(La, ++La_len,e); } }

2.2

顺序表存储的Ｃ语言实现

静态分配 #define MaxSize 100 // 线性表的最大长度 typedef　struct { ElemType data[MaxSize]; int length; // 当前长度 }SqList； 动态分配 #define InitSize 100 //空间初始分配量 typedef　struct { ElemType *data; // 指示动态分配数组的指针 int length; // 当前长度 int MaxSize; // 数组的最大容量 }SqList； // C L.data = (ElemTpye*)malloc(sizeof(ElemType)*InitSize); // C++ L.data = new ElemType[InitSize];

创建一个空的顺序表（算法2.3）

// 引用 Status InitList(SqList &L) { // 分配 L.data = (ElemTpye*)malloc(sizeof(ElemType)*InitSize); // 分配失败 if (!L.data) exit(OVERFLOW); // 线性表的当前长度0 L.length = 0; // 线性表的存储容量 L.MaxSize = MAX_SIZE; return OK; }

用类C语言实现顺序表的插入

// 王道 // 数组从0开始 // 插入到第i个位置[1, n] bool InsertList(SqList &L, int i,ElemType e) { // 合法：插入到的第i个[1, n+1]，n+1表示表尾增加 if(i < 1 || i > L.length + 1) { return false; } // 满了 if(L.length >= MaxSize) { return false; } // 后移，倒着，对应数组下标[i-1,n-1]→[i,n] for(int j = L.length; j >= i; j--) { L.data[j] = L.data[j-1]; } // 第i个对应数组下标i-1 L.data[i-1] = e; L.length++; return true; } // 野生PPT // 这里是C语言的数组定义（从0开始），而不是伪代码的数组定义（从1开始） // 将元素x插入在线性表L的第i个元素位置上，即对应下标i-1。注意，是第几个位置，不是直接插入下标 Status ListInsert_sq(SqList &L, int i, ElemType x) { // 越界 if (i < 1 || i > L.length + 1) return ERROR; // 没用存储空间，要新增 if (L.length >= L.Listsize) { // 重新分配 realloc，大小是 原来的listsize + LISTINCREMENT 增量 newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); // 分配失败 if (!newbase) exit(OVERFLOW); // 线性表的存储空间基址更新 L.elem = newbase; // 线性表的容量更新 L.listsize += INCREMENT; } // q为插入位置, C语言数组下标从0开始 q = &(L.elem[i - 1]); // 移动元素并插入，倒着从最后一个开始，到包括要插入的那个位置 for (p = &(L.elem[L.length - 1]); p >= q; --p) { // 后一个元素赋值前一个，表示后移元素 *(p + 1) = *p; } // 空出来的位置就是要插入的元素 *q = x; // 线性表的当前长度更新 L.length++; return OK; } //ListInsert_sq

删除

// 王道 // 数组从0开始 // 删除到第i个位置[1, n] bool ListDelete(SqList &L, int i, ElemType &e) { // 合法：删除的第i个[1, n] if(i < 1 || i > L.length) { return false; } // 对应 e = L.data[i-1]; // 前移：对应数组[i, n-1]→[i-1, n-2] for(int j=i; j<L.length;j++) { L.data[j-1] = L.data[j]; } L.length--; return true; }

按值查找（顺序查找）

// 王道 // 数组从0开始 // 成功返回第i个位置[1, n]，失败返回0 int LocateELem(SqList L, ElemType e) { for(int i = 0; i < L.length; i++) { // 数组下标i对应第i+1个 if(L.data[i] == e) return i+1; } return 0; }

2.3

2.3.1.单链表

单链表的C语言实现

typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 } LNode, *LinkList; // LinkList表示结点的指针

用类C语言实现单链表上的查询(查找第i个元素)：

// L是带头结点的单链表的头指针，注意头结点的特殊含义（第一个结点没有数据，第二个结点才是第一个元素）。 // i表示第i个元素，而不是下标 // 效果：当第i个元素存在时，将该元素的值赋给e并返回OK，否则返回ERROR Status GetElem_L(LinkList L, int i, ElemType &e) { // 初始化，p指向第一个元素，k为计数器 p = L->next; // k=1，从第一个元素开始，保证了i<1的非法情况直接排除 k = 1; // 顺指针向后查找：p不空表示合法结点，k<i表示还要继续遍历 while (p && k < i) { p = p->next; ++k; } // 循环的退出条件为 到达单链表结尾(P为空) 或 k=i（没找到，或找到了） // 第i个元素不存在（空，遍历完没找到） if (!p || k > i) return ERROR; // 赋值 e = p->data; return OK; } //GetElem_L

查找第[1,n]个元素处，p对应第[1,n]个元素

思考: “本算法为何没有考虑 i值的合法性？” 两种非法：i<1和 i>n

i<1（i<=0）：因为while的循环条件k < i，此时k>i，非法情况直接排除。i>n：p空了。

单链表上的插入运算(第i个元素位置上插入新的结点)

// 在带头结点的单链表L中第i个元素位置之前插入元素e // 第i个 Status ListInsert_L(LinkList &L, int i, ElemType e) { // 初始化，p指向头结点，k为计数器 p = L; // k=0，表示找到的是i前的那个元素，还保证了i<1的非法情况直接排除 k = 0; // 遍历，p不空，k<i-1（++k出来就是k=i-1） while (p && k < i - 1) { p = p->next; ++k; } // 逐步移动指针p，直到 p为空 或 p指向第i-1个元素 // 第i个元素不存在（p空，遍历完没找到） if (!p || k > i - 1) return ERROR; // 申请元素e的结点空间，并判断失败否 if (!(s = (LinkLinst)malloc(sizeof(LNode)))) return OVERFLOW; // 对应②赋值e s->data = e; // 对应③ s->next = p->next; // 对应④ p->next = s; return OK; } //LinstInsert_L

合法区间：插入到第[1,n+1]个元素处，p对应第[0,n]个元素。

i<1：失败。i>n+1：失败。

单链表上的删除运算(把第i个元素删除)

// 在带头结点的单链表L中，删除第i个元素，并由e返回其值 // 第i个 Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 初始化，p指向头结点，k为计数器 p = L; // k=0，表示找到的是i前的那个元素，还保证了i<1的非法情况直接排除 k = 0; // 遍历，p的下一个结点不空，k<i-1（++k出来就是k=i-1） while (p->next && k < i - 1) { p = p->next; ++k; } // 第i个元素不存在（p->next空，遍历完没找到） if (!p->next || k > i - 1) return ERROR; // 对应②：增设临时指针q指向p的下一结点(待删除的结点)； q = p->next; // 对应③：修改结点p的指针域，指向第i-1个结点(p->next=p->next ->next)； p->next = q->next; // 由e返回其（要删除的结点）值 e = q->data; // 对应④：删除结点q，释放内存空间。 free(q); return OK; } //ListDelete_L

思考： while语句中的p->next 可否用p替代？ 不行，因为要保证p的下一个结点不能空。

合法区间：第[1,n]个元素，p对应第[0,n-1]个元素

用类C语言实现表头插入算法：

// 用表头插入法逆序建立带头结点的单链表 void CreateList_L(LinkLinst &L, int n) { // 未做溢出判定，应加入 L = (LinkList)malloc(sizeof(LNode)); // 带头结点的空链表 L->next = NULL; // 建立头结点，假定与元素结点结构相同 // 因为是逆序，所以从后向前输入元素 for (i = n; i > 0; --i) { // 生成新结点 p = (LinkList)malloc(sizeof(LNode)); // 从键盘输入元素值，存入新结点中 scanf(&p->data); // 新结点的下一个结点是头结点的下一个结点 p->next = L->next; // 头结点的下一个结点是新节点 L->next = p; } }

用C语言实现表头插入算法：

#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; void ListDelete_L(LinkList &L, int n) { // 未做溢出判定，应加入 L = (LinkList)malloc(sizeof(LNode)); // 空链表 L->next = NULL; // p为指向结点的指针类型 LinkList p = NULL; for (int i = n; i > 0; --i) { //从后向前输入元素 p = (LinkList)malloc(sizeof(LNode)); //未做溢出判定，应加 scanf("% d", &p->data);//将键盘输入置入p的数据域 p->next = L->next; L->next = p; } }

用类C语言实现两个有序单链表的合并

// 归并两个非递减带头结点的单链表La、Lb到Lc中（相同项都保留），且使Lc非递减 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) { // 用于遍历的指针指向第一个元素 pa = La->next; pb = Lb->next; // 带头结点的空链表 Lc = (LinkList)malloc(sizeof(LNode)); Lc->next = NULL; // 用于遍历的指针 pc = Lc; // 都不为空 while (pa && pb) { if (pa->data <= pb->data) { // pc的下一个结点接pa pc->next = pa; // pc更新为最后一个 pc = pa; // pa更新为下一个 pa = pa->next; } else { // pc的下一个结点接pb pc->next = pb; // pc更新为最后一个 pc = pb; // pb更新为下一个 pb = pb->next; } } // 至少一个链表走完了，那就不用比较了，直接接另一个链表的剩下部分 pc->next = pa ? pa : pb; } // MergeList_L

2.3.2.循环单链表和双向链表

双向链表的C语言描述

typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DulinkList;