1.单链表的定义typedef struct LNode{ //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode, *LinkList;单链表是一种非随机存取的存储结构。当头指针为NULL时表示链表为空。在带头结点的单链表中头指针L指向头结点而头结点的next指向第一个数据节点。在不带头结点的单链表中头指针L直接指向第一个数据结点。2.单链表上基本操作的实现2.1 单链表的初始化bool InitList(LinkList L){ //带头结点的单链表初始化 L(LNode*)malloc(sizeof(LNode)); //创建头结点 L-nextNULL; //头节点之后暂无数据结点 return true; }不带头结点的单链表初始化时只需将头指针L初始化为NULL。bool InitList(LinkList L){ //不带头结点的单链表初始化 LNULL; return true; }2.2 求表长操作求表长是指统计单链表中数据结点的个数不包括头结点int Length(LinkList L){ int len0; //计数变量初始为0 LNode *pL; while(p-next!NULL){ pp-next; len; //每访问一个结点计数加1 } return len; }求表长操作的时间复杂度为O(n)O(n)O(n)。2.3 按序号查找结点LNode *GetElem(LinkList L, int i){ LNode *pL; //指针p指向当前扫描结点。 int j0; //j记录当前位序头结点为第0个结点。 while(p!NULLji){ //循环找到第i个结点 pp-next; j; } return p; //返回第i个节点的指针或NULL }按序号查找操作的时间复杂度为O(n)O(n)O(n)。2.4 按值查找表结点LNode *LocateElem(LinkList L, elemtype e){ LNode *pL-next; while(p!NULLp-data!e) //从第一个结点开始擦汗中阿数据域为e的节点 pp-next; return p; //找到后返回该结点指针否则返回NULL }按值查找操作的时间复杂度为O(n)O(n)O(n)。2.5 插入结点操作bool ListInsert(LinkList L, int i, Elemtype e){ LNode *pL; //p指向当前扫描结点 int j0; //j记录当前位序头结点为第0个结点 while(p!NULLji-1){ //循环找到第i-1个结点 pp-next; j; } if(pNULL) //i值不合法 return false; LNode *s(LNode*)malloc(sizeof(LNode)); s-datae; s-nextp-next; //(1) p-nexts; //(2) return true; }时间复杂度为O(n)O(n)O(n)。(1)和(2)的顺序不可颠倒。扩展对某个节点进行前插操作。前插操作是指在某结点前插入一个新结点与后插操作相反。主要代码片段如下s-nextp-next; //修改指针域不能颠倒 pnexts; tempp-data; //交换数据域部分 p-datas-data; s-datatemp;时间复杂度为O(n)O(n)O(n)。2.6 删除结点操作bool ListDelete(LinkList L, int i, ElemType e){ LNode *pL; //指针p指向当前扫描到的结点 int j0; //记录当前结点的位序头结点是第0个结点 while(p-next!NULLji-1){ //循环找到第i-1个结点 pp-next; j; } if(p-nextNULL||ji-1) //i值不合法 return false; LNode *qp-next; //令q指向被删除结点 eq-data; //用e返回元素的值 p-nextq-next; //将*q节点从链中“断开” free(q); //释放节点的存储空间 return true; }时间复杂度为O(n)O(n)O(n)。扩展删除给定结点*p。主要代码片段LNode *qp-next; //令q指向*p的后继结点 p-datap-next-data; //用后继结点的数据域覆盖 p-nextq-next; //将*q节点从链中“断开” free(q); //释放后继结点的存储空间时间复杂度为O(n)O(n)O(n)。2.7 采用头插法建立单链表LinkList List_HeadInsert(LinkList L){ //逆向建立单链表 LNode *s; int x; //设元素类型为整数 L(LNode*)malloc(sizeof(LNode)); //创建头结点 L-nextNULL; //初始为空链表 scanf(%d, x); //输入结点的值 while(x19999){ //输入9999表示结束 s(LNode*)malloc(sizeof(LNode)); //创建新结点 s-datax; s-nextL-next; L-nexts; //将新结点插入表中L为头结点 scanf(%d, x); } return L; }每插入一个结点的时间复杂度为O(1)O(1)O(1)总时间复杂度为O(n)O(n)O(n)。2.8 采用尾插法建立单链表LinkList List_TailInsert(LinkList L){ //正向建立单链表 int x; //设元素类型为整数 L-(LNode*)malloc(sizeof(LNode)); //创建头结点 LNode *s, *rL; //r为表尾指针 scanf(%d, x); //输入结点的值 while(x!9999){ //输入9999表示结束 s(LNode*)malloc(sizeof(LNode)); s-datax; r-nexts; rs; //r指向新的表尾结点 scanf(%d, x); } r-nextNULL; //尾节点置空 return L; }因为附设了一个尾指针故无须遍历查找尾部总时间复杂度为O(n)O(n)O(n)。3.双链表3.1 双链表的定义typedef struct DNode{ //定义双链表结点类型 ElemType data; //数据域 struct DNode *prior,*next; //前驱和后继指针 }DNode, *Dlinklist;3.2 双链表的插入操作核心代码片段如下s-nextp-next; p-next-priors; s-priorp; p-nexts;3.3 双链表的删除操作p-nextq-next; q-next-priorp; free(q);4.静态链表定义#define MaxSize 50 //静态链表的最大长度 typedef struct{ //静态链表的结构类型定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 } SLinkList[MaxSize];
