数据结构的线性表

一、顺序表线性结构的特点是1、存在唯一的一个被称作“第一个”的数据元素2、存在唯一的一个被称作“最后一个”的数据元素3、除第一个之外集合中的每个元素均只有一个前驱4、除最后一个以外集合中的每个数据元素均只有一个后继两种表现形式顺序表数组和链表结构体顺序表示与实现#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ ElemType *elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { // 分配内存空间大小为LIST_INIT_SIZE 乘以ElemType的大小 L-elem (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (L-elem NULL) { return OVERFLOW; // 如果内存分配失败返回溢出错误 } L-length 0; // 初始化顺序表的长度为 0 L-listsize LIST_INIT_SIZE; // 初始化顺序表的容量为LIST_INIT_SIZE return OK; }顺序表的插入int ListInsert_Sq(SqList *L, int i, ElemType e) { // 判断插入位置是否合法i的值应该在1 到L.length1 之间 if (i 1 || i L-length 1) { return ERROR; } // 如果顺序表已满需要重新分配内存空间 if (L-length L-listsize) { ElemType *newbase (ElemType*)realloc(L-elem, (L-listsize LISTINCREMENT) * sizeof(ElemType)); if (!newbase) { exit(OVERFLOW); // 内存分配失败退出程序 } // 更新顺序表的基地址和容量 L-elem newbase; L-listsize LISTINCREMENT; } // 找到插入位置的地址 ElemType *q (L-elem[i - 1]); // 将插入位置之后的元素向后移动一位 for (ElemType *p (L-elem[L-length - 1]); p q; --p) { *(p 1) *p; } // 将新元素插入到指定位置 *q e; L-length; // 更新顺序表的长度 return OK; }顺序表的删除int ListDelete_Sq(SqList *L, int i, ElemType *e) { // 判断删除位置是否合法i的值应该在1 到L.length之间 if (i 1 || i L-length) { return ERROR; } // 找到删除位置的地址 ElemType *p (L-elem[i - 1]); // 将删除位置的元素赋值给e *e *p;// 将删除位置之后的元素向前移动一位 ElemType *q L-elem L-length - 1; for (p; p q; p) { *(p - 1) *p; } // 更新顺序表的长度 --L-length; return OK; }时间复杂度Eis为插入E(dl)为删除顺序表的合并void MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc) { ElemType *pa, *pb, *pc; ElemType *pa_last,*pb_last; // 初始化指针pa 和pb分别指向顺序表La 和Lb的第一个元素 pa La-elem; pb Lb-elem; // 初始化Lc 的大小并分配内存空间 Lc-listsize Lc-length La-length Lb-length; Lc-elem (ElemType *)malloc(Lc-listsize * sizeof(ElemType)); if (!Lc-elem) { exit(OVERFLOW); // 如果内存分配失败退出程序 } pc Lc-elem;// 初始化指针pc指向顺序表Lc 的第一个元素 // 初始化指针pa_last和pb_last分别指向顺序表La 和Lb的最后一个元素 pa_last La-elem La-length - 1; pb_last Lb-elem Lb-length - 1; while (pa pa_last pb pb_last) { //合并两个顺序表直到其中一个顺序表遍历完 if (*pa *pb) { *pc *pa; // 将较小的元素放入Lc } else { *pc *pb; } } while (pa pa_last) { // 如果pa没有到达最后一个元素将剩余的元素插入到Lc中 *pc *pa; } while (pb pb_last) { // 如果pb没有到达最后一个元素将剩余的元素插入到Lc中 *pc *pb; } }二、线性列表typedef struct LNode{ //创建列表 ElemType data; struct LNode *next; }LNode,*LinkList; void CreateList_L(LinkList *L, int n) { L (LinkList)malloc(sizeof(LNode)); L-next NULL; for (int i n; i 0; i--) { LNode *p (LNode *)malloc(sizeof(LNode)); scanf(%d, p-data); p-next L-next; L-next p; } }int ListInsert_L(LinkList *L, int i, ElemType e) { //插入节点 LinkList p *L; // 用指针 p 指向头节点 int j 0; // 遍历链表直到找到第 i-1 个节点 while (p j i - 1) { p p-next; j; } // 如果遍历到链表末尾说明i的值不合法返回ERROR if (!p || j i - 1) { return ERROR; } // 创建一个新节点s将新节点插入到第i-1 个节点之后 LinkList s (LinkList)malloc(sizeof(LNode)); // 为新节点分配内存 if (!s) { return ERROR; // 如果内存分配失败返回ERROR } s-data e; // 将数据e 插入到新节点中 s-next p-next; // 将新节点的next 指向原来第i个节点 p-next s; // 将第i-1 个节点的next 指向新节点 return OK; // 插入成功返回OK }int GetElem_L(LinkList L, int i, ElemType *e) { //查找节点 LinkList p L-next; // 指针p 指向链表的第一个元素 int j 1;// 从头节点开始遍历链表直到找到第i个节点或者遍历到链表末尾 while (p j i) { p p-next; j; } // 如果遍历到链表末尾说明i的值不合法返回ERROR if (!p || j i) { return ERROR; } // 将第i个节点的值赋值给e *e p-data; return OK; }// 删除链表L 中第i个元素并将其值存入e int ListDelete_L(LinkList *L, int i, ElemType *e) { LinkList p *L; // 指针p 指向头节点 LinkList q; // 用于保存要删除的节点 int j 0;// 从头节点开始遍历链表找到第i-1 个节点 while (p-next j i - 1) { p p-next; j; } // 如果遍历到链表末尾说明i的值不合法返回ERROR if (!(p-next) || j i - 1) { return ERROR; } // 删除第i个节点并将其值赋值给e q p-next; // 保存要删除的节点 p-next q-next; // 将第i-1 个节点的next 指向第i1 个节点 *e q-data; // 将被删除节点的值赋给e free(q); // 释放被删除节点的内存 return OK; // 删除成功返回OK }void MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc) { LinkList pa (*La)-next; // 指向链表 La 的第一个节点 LinkList pb (*Lb)-next; // 指向链表Lb的第一个节点 LinkList pc; // 用于构建链表Lc *Lc pc *La; // 将Lc 的头节点指向La并将pc 也指向La // 当pa 和pb 都不为NULL 时比较它们的值将较小的节点插入到Lc 中 while (pa pb) { if (pa-data pb-data) { pc-next pa; pc pa; pa pa-next; } else { pc-next pb; pc pb; pb pb-next; } } // 如果pa 不为NULL将剩余的节点插入到Lc 中 pc-next pa ? pa : pb; // 释放链表Lb的头节点避免内存泄漏 free(*Lb); }