注： 所有代码块均来自《大话数据结构》第二版

线性表

线性表的定义和抽象数据类型线性表的顺序存储结构顺序存储结构的代码顺序存储结构的存入或取出顺序存储结构的插入或删除 线性表的链式存储结构单链表单链表的存储结构单链表的读取单链表的插入和删除单链表的整表创建单链表的整表删除 静态链表静态链表存储结构静态链表的插入静态链表的删除 循环链表双向链表

线性表的定义和抽象数据类型

List 定义： 零个或多个数据元素的有限序列抽象数据类型 ADT 线性表 （List） Data Operation InitLIst(*L); /*初始化操作，建立一个空的线性表L*/ ClearList(*L); /*清空线性表L*/ ListEmpty(L); /*若线性表为空，返回true，否则返回false*/ ListLength(L); /*返回线性表L的元素个数*/ GetElem(L, i, *e); /*将线性表第i个元素赋值给e*/ LocatedElem(L, e); /*查找与e的值相等的元素，如果查找成功，返回该元素在表中的序号表示成功； 否则返回0表示失败*/ ListInsert(*L, i, e); /*在L的第i个位置插入新元素e*/ listDelete(*L, i, *e); /*删除线性表L中第i个位置元素，并用e返回其值*/ endADT

线性表的顺序存储结构

顺序存储结构的代码

# define MAXISIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXISIZE]; int length; }SqList;

顺序存储结构的存入或取出

随机存取，时间复杂度为O(1)

顺序存储结构的插入或删除

/*获得元素操作*/ #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /*Status是函数的类型，其值是函数结果的返回代码，如OK等*/ Status GetElem(SqList L, int i, ElemType *e) { if (L.length==0 || i<1 || i>L.length) return ERROR; *e = L.data[i]; return OK; } /*插入*/ Status ListInsert(SqList *L, int i, ElemType e) { int k; if (L->length == MAXSIZE) return ERROR; if (i < 1 || i > L->length+1) return ERROR; if (i <= L.length) { for (k=L->length-1, k>=i-1, k--) { L->data[k+1] = L->data[k]; } } L->data[i-1] = e; L->length++; return OK; } /*删除*/ Status ListDelete(SqList *L, int i, ElemType *e) { if (L->length == 0) return ERROR; if (i<1 || i>L->length) return ERROR; *e = L->data[i-1]; for (k=i, k<L->length, k++) { L->data[k-1] = L->data[k]; } L->length--; return OK; }

线性表的链式存储结构

单链表

定义： n个结点链结成一个链表，且每个结点中只包含一个指针域结点组成元素 数据域：存储data指针域：存储指针/链 头指针：链表中第一个结点的存储位置，必须有头结点：头结点的指针域指向第一个有信息的结点，空链表指针域为NULL

单链表的存储结构

typedef struct Node { ElemType data; struct Node *next; } Node; typedef struct Node *LinkList;

单链表的读取

Status GetElem(LinkList L, int i, Elemtype *e) { LinkList p; p = L->next; int j = 1; while(p && j<i) { p = p->next; /*第寻找i个节点*/ ++j; } if (!p || j>i) /* 前者为空链表或者链表长度小于索引i，后者为i小于1的情况*/ return ERROR; *e = p->data; return OK; }

单链表的插入和删除

/*插入*/ Status ListInsert(LinkList *L, int i , ElemType e) { int j = 1; LinkList p, s; p = *L; while(p && j<i) { p = p->next; /*第寻找i-1个节点*/ ++j; } if (!p || j>i) return ERROR; s = (LinkList)malloc(sizeof(Node)) s->data = e; s->next = p->next; p->next = s; return OK; } /*删除*/ Status ListDelete(LinkList *L, int i, ElemType *e) { int j = 1; LinkList p,q; p = *L; while(p && j<i) { p = p->next; ++j; } if(!(p->next) || j>i) return ERROR; q = p->next; p->next = q->next; *e = q->data; free(q); return OK; }

单链表的整表创建

/*头插法*/ void CreateListHead(LinkList *L, int n) { LinkList p; int i = 0; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); /*头结点*/ (*L)->next = NULL; for(i=0; i<n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand()%100+1; /*随机生成100以内的数字*/ p->next = (*L)->next; (*L)->next = p; } } /*尾插法*/ void CreatList(LinkList *L, int n) { LinkList p; int i = 0; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); r = *L; for(i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)) p->data = rand()%100+1; r->next = p; r = p } r->next = NULL; }

单链表的整表删除

Status ClearList(LinkList *L) { LinkList p,q; p = *L; while(p) { q = p->next; free(p); p = q; } (*L)->next = NULL; return OK; }

静态链表

用数组代替指针描述单链表，静态链表备用链表：未被使用的数组元素数组的第一个和最后一个元素不存数据数组的第一个元素的cur存放备用链表的第一个结点的下标数组的最后一个元素存放第一个有数值的元素下标，相当于头结点当整个链表为空时，最后一个元素的cur存放0

静态链表存储结构

#define MAXSIZE 1000 typedef struct { ElemType data; int cur; }Component, StaticLinkList[MAXSIZE] /*创建空链表*/ Status InitList(StaticLinkList space) { int i; for(i=0; i<MAXSIZE-1； i++) { space[i].cur = i+1; } space[MAXSIZE-1].cur = 0; return OK; }

静态链表的插入

int ListLength(StaticListLength L) { int j = 0; int i = L[MAXSIZE-1].cur; while(i) { i = L[i].cur; j++; } return j; } int Malloc_SLL(StaticLinkList space) { int i = space[0].cur; /*备用链表的第一个下标*/ if （space[0].cur） space[0].cur = space[i].cur; return i; } Status ListInsert(StaticLinkList L, int i, ElemType e) { int j,k,l; k = MAXSIZE-1; if(i<1 || i > ListLength(L)+1) return ERROR; j = Malloc_SLL(L); if(j) { for(l=1; l<=i-1; l++) { k = L[k].cur; } L[j].cur = L[k].cur; L[k].cur = j; return Ok; } return ERROR; }

静态链表的删除

void Free_SLL(StaticLinkList space, int k) { space[k].cur = space[0].cur; space[0].cur = k; } Status ListDelete(StaticLinkList L, int i) { if(i<1 || i > ListLength(L)) return ERROR; k = MAXSIZE - 1; for (l=1; l<=i-1; l++) { k = L[k].cur; } j = L[k].cur; L[k].cur = L[j].cur; Free_SLL(L,j) return OK; }

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，即 LinkList L; rear->next = L->next; 将两个循环链表合并 LinkList p, q; p = rearA->next; q = rearB->next; rearA->next = q->next; rearB->next = p; free(q);

双向链表

双向链表 数据直接前驱指针直接后继指针 typedef struct DulNote { ElemType data; Struct DulNote *prior; Struct DulNote *next; }DulNode, *DuLinkList; 插入 DuLinkList p,s; s -> prior = p; s -> next = p->next; p->next->prior = s; p->next = s;