线性表

概述

• 线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。
• 线性表的逻辑特性是除第一个元素外，每个元素有且只有一个直接前驱元素，除了最后一个元素外，每个元素有且只有一个直接后继元素。
• 线性表的存储结构有两种：顺序存储结构（顺序表）和链式存储结构（链表）。顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，链表是用一组任意的存储单元存储数据元素，并用指针域表示元素之间的逻辑关系。
• 线性表的基本操作包括初始化、求表长、按值查找、按位查找、插入、删除、输出、判空、销毁等。不同的存储结构对应不同的实现方法和时间复杂度。
• 线性表是一种常用的数据结构，它可以表示一些具有线性关系的数据集合，如数组、字符串、栈、队列、广义表等。

线性表的特点

• 表中元素的个数是有限的。
• 表中元素的数据类型相同。即每一个元素占用相同大小的空间。
• 表中元素具有逻辑上的顺序性，在序列中个元素排序有其先后顺序。

线性表的基本操作

• 初始化操作：InitList(&L)。构造一个空的线性表L，分配内存空间。
• 插入操作：ListInsert(&L,i,e)。在表L中的第i个位置上插入指定元素e，如果i不合法或表满，则返回false，否则返回true。
• 删除操作：ListDelete(&L,i,&e)。删除表L中第i个位置的元素，并用e返回删除元素的值，如果i不合法或表空，则返回false，否则返回true。
• 按值查找操作：LocateElem(L,e)。在表L中查找具有给定关键字值的元素，如果查找成功，则返回元素在表中的序号，否则返回0。
• 按位查找操作：GetElem(L,i)。获取表L中第i个位置的元素的值，如果i不合法，则返回false，否则返回true。
• 输出操作：PrintList(L)。按前后顺序输出线性表L的所有元素值。
• 判空操作：Empty(L)。若L为空表，则返回true，否则返回false。
• 销毁操作：DestroyList(&L)。销毁线性表，并释放线性表L所占用的内存空间。

线性表的顺序表示

概述

顺序表是一种线性表的存储结构，它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。顺序表通常用数组来实现，可以方便地随机访问任意位置的元素。

优缺点

• 顺序表的优点：
  • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
  • 可以快速地存取表中任一位置的元素，实现随机访问。
• 顺序表的缺点：
  • 插入和删除操作需要移动大量元素，效率较低。
  • 当线性表长度变化较大时，难以确定存储空间的容量，可能造成存储空间的浪费或不足。

操作

顺序表的定义

• 顺序表的定义：顺序表是用一个数组来存放线性表中的数据元素，同时还需要记录顺序表的长度和容量。长度表示当前顺序表中有效元素的个数，容量表示顺序表能够存放的最大元素个数。

  //顺序表的定义
  #define MaxSize 50
  typedef int ElemType;//顺序表中元素的类型
  //静态分配
  typedef struct {ElemType data[MaxSize];//定义数组用来存储元素int length;//当前顺序表中有多少个元素
  }SqList;

顺序表的初始化

• 顺序表的初始化：顺序表初始化需要给数组动态分配一定大小的内存空间，并将长度和容量赋初值。如果内存分配失败，需要提示错误并退出程序。

  //顺序表的初始化
  void InitList(SeqList &L) {L.length = 0; //初始长度为0
  }
  

顺序表的插入

• 顺序表的插入：顺序表插入需要在指定位置插入一个新元素，如果插入位置不合法或者顺序表已满，需要返回false，否则返回true。插入操作可能需要移动后面的元素，以保持元素的连续性。插入后，顺序表的长度增加1。

  

  • 最好情况：在表尾插入元素，不需要移动元素，时间复杂度为O(1)
  • 最坏情况：在表头插入元素，所有元素依次后移，时间复杂度为O(n)
  • 平均情况：在插入位置均等的情况下，平均移动元素的次数是n/2,时间复杂度为O(n)

  /* 顺序表的插入* @param L 要插入的表* @param i 插入的位置* @param e 插入的值* @return 返回true或者false*/
  bool ListInsert(SqList &L,int i,ElemType e)
  {if (i<1||i>L.length+1)return false;//判断插入的位置是否合法if (L.length>=MaxSize)return false;//超出最大长度for (int j = L.length; j >=i; j--) {    //从最后一位元素依次向后移动一位，到索引为i为止L.data[j]=L.data[j-1];}//插入元素L.data[i-1]=e;//表长度加1L.length++;//返回true，表示插入成功return true;
  }

顺序表的删除

• 顺序表的删除：顺序表删除需要删除指定位置的元素，并用一个变量返回被删除元素的值，如果删除位置不合法或者顺序表为空，需要返回false，否则返回true。删除操作可能需要移动后面的元素，以保持元素的连续性。删除后，顺序表的长度减少1。

  

  • 最好情况：删除表尾元素，不需要移动元素，时间复杂度为O(1)
  • 最坏情况：删除表头元素，所有元素依次前移，时间复杂度为O(n)
  • 平均情况：在删除位置均等的情况下，平均移动元素的次数是n/2,时间复杂度为O(n)

  //顺序表的删除
  bool ListDelete(SeqList &L, int i, ElemType &e) {if (i < 1 || i > L.length) return false; //判断删除位置是否合法e = L.data[i - 1]; //用e返回被删除元素的值for (int j = i; j < L.length; j++) { //从前往后移动元素，填补空位L.data[j - 1] = L.data[j];}L.length--; //长度减1return true;
  }
  

顺序表的查找

• 顺序表的查找：顺序表查找可以按值查找或按位查找。按值查找是在顺序表中找到第一个与给定值相等的元素，并返回其位置，如果没有找到，则返回0。按位查找是获取顺序表中指定位置的元素的值，如果位置不合法，则返回false，否则返回true。

  //顺序表的按值查找
  int LocateElem(SeqList L, ElemType e) {for (int i = 0; i < L.length; i++) { //遍历顺序表，比较每个元素与e是否相等if (L.data[i] == e) return i + 1; //如果找到，返回元素在表中的位置}return 0; //如果没找到，返回0
  }//顺序表的按位查找
  bool GetElem(SeqList L, int i, ElemType &e) {if (i < 1 || i > L.length) return false; //判断查找位置是否合法e = L.data[i - 1]; //用e返回第i个元素的值return true;
  }
  

顺序表的输出

• 顺序表的输出：顺序表输出是按照前后顺序打印出顺序表中所有元素的值。

  /* 打印线性表元素* @param L 要打印元素的线性表*/
  void println(SqList &L)
  {for (int i=0;i<L.length;i++) //遍历打印顺序表每一个元素{printf("%4d",L.data[i]);}printf("\\n");
  }
  

顺序表的判空

• 顺序表的判空：顺序表判空是判断顺序表是否为空，即长度是否为0，如果为空，则返回true，否则返回false。

  /* 顺序表的判空* @param L 要判空的顺序表* @return 如果长度为0，返回true，否则返回false*/
  bool Empty(SqList L) {return L.length == 0; //如果长度为0，返回true，否则返回false
  }
  

顺序表的销毁

• 顺序表的销毁：顺序表销毁是释放数组所占用的内存空间，并将长度和容量置为0。

  /* 顺序表的销毁（C++中不需要手动释放数组空间）* @param L 要销毁的表*/
  void DestroyList(SqList &L) {L.length = 0; //将长度置为0即可
  }
  

main方法测试

int main(){SqList L; //顺序表的名称InitList(L);bool ret;//查看返回值，布尔型是true,或falseElemType del;//要删除的元素或查找的元素//首先手动在顺序表中赋值L.data[0]=1;L.data[1]=2;L.data[2]=3;L.length=3;//总计三个元素//插入元素ret = ListInsert(L,2,60); // 在顺序表第二个位置插入60if (ret){printf("插入成功\\n");println(L); // 插入成功，打印顺序表} else{printf("插入失败\\n");}//删除元素ret = ListDelete(L,2,del);if (ret){printf("删除成功\\n");println(L); // 删除成功，打印顺序表} else{printf("删除失败\\n");}//顺序表的按值查找ElemType index = LocateElem(L,2);if (index){printf("查找成功\\n");printf("index: %d\\n",index);} else{printf("查找失败\\n");}//顺序表的按位查找ret = GetElem(L,2,del);if (ret){printf("成功\\n");printf("ret:%d\\n",del);} else{printf("失败\\n");}printf("%d", Empty(L));DestroyList(L);println(L);return 0;
}

线性表的链式表示

概述

线性表的链式表示是一种用链表来存储线性表的数据结构。链表由一系列结点组成，结点的不同可以分成单链表和双链表。链表的第一个结点称为头结点，最后一个结点称为尾结点。

单链表和双链表是两种不同的链式存储结构，它们的概述如下：

• 单链表：每个结点只有一个指针域，指向其后继结点。单链表有头指针，可以有或没有头结点。单链表的插入和删除操作只需要修改指针，但不能随机访问元素，只能从头结点开始顺序遍历。头结点通常不存储数据元素，而是用来方便地访问链表。尾结点的指针域为空，表示链表的结束。

  

  

• 双链表：每个结点有两个指针域，分别指向其前驱结点和后继结点。双链表有头指针和尾指针，通常也有头结点和尾结点。双链表的插入和删除操作需要修改两个指针，但可以双向遍历元素，方便查找前驱和后继。双链表的尾结点的指针域不为空，而是指向头结点，形成一个循环链表。头结点的指针域也不为空，而是指向第一个数据结点。头结点和尾结点相互指向，构成一个环。

优缺点

• 优点：
  • 插入和删除操作不需要移动大量元素，只需要修改指针即可，时间复杂度为O(1)。
  • 不需预先分配空间，由系统根据需求动态分配，存储空间利用率高。
  • 可以存储任意大小和类型的数据元素，存储密度不受限制。
• 缺点：
  • 增加了指针域的存储开销，降低了存储密度。
  • 不可以随机访问数据元素，只能从头结点开始顺序遍历，时间复杂度为O(n)。
  • 链表的操作需要频繁地申请和释放内存空间，可能造成内存碎片。

单链表操作

单链表的定义

• 单链表的定义：单链表是一种链式存取的数据结构，每个结点包含一个数据域和一个指针域，数据域存储数据元素，指针域指向下一个结点，通过指针域将线性表的数据元素按其逻辑次序链接在一起。

//定义一个结点结构体
typedef int ElemType;//单链表中元素的类型
typedef struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList;

单链表的初始化

• 单链表的初始化：创建一个空的单链表，也就是只有一个头结点，没有其他结点。头结点的数据域可以不存储任何信息，也可以存储单链表的长度或其他信息。头结点的指针域必须置空，表示单链表没有第一个结点。

/* 初始化单链表* @param L 链表头结点*/
void InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode)); //分配头结点空间if(L == NULL) exit(-1); //分配失败退出L->next = NULL; //头结点的指针域置空
}

单链表的头插法

• 单链表的头插法：将新结点插入到链表的头部，使得新结点成为第一个结点。

/* 头插法创建单链表* @param L 要插入的单链表*/
void CreateList_Head(LinkList &L){//引用可加可不加ElemType x = 0;//输入的数据scanf("%d",&x);//读入第一个数据while(x != 9999){ //用9999作为结束标志LNode *s = (LNode *)malloc(sizeof(LNode)); //分配新结点空间if(s == NULL) exit(-1); //分配失败退出s->data = x; //新结点的数据域赋值为xs->next = L->next; //新结点的指针域指向原第一个结点L->next = s; //头结点的指针域指向新结点scanf("%d",&x);//读入下一个数据}
}

单链表的尾插法

• 单链表的尾插法：将新结点插入到链表的尾部，使得新结点成为最后一个结点。

/* 尾插法创建单链表* @param L 链表头结点*/
void CreateList_Tail(LinkList &L){//引用可加可不加ElemType x;//输入的数据LNode *tailNode = L; //tailNode指向尾结点，初始时指向头结点scanf("%d",&x); //读入第一个数据while (x!=9999){ //用9999作为结束标志LNode *s = (LinkList) malloc(sizeof(LNode)); //分配新结点空间if (s == NULL) exit(-1); //分配失败退出s->next = NULL; //尾结点的指针域置空s->data = x; //新结点的数据域赋值为xtailNode->next = s; //原尾结点的指针域指向新结点tailNode = s; //tailNode指向新的尾结点scanf("%d",&x); //读入下一个数据}// tailNode->next =NULL
}

单链表的按序号查找

• 单链表的按序号查找：按序号查找是一种在单链表中根据给定的位置查找对应的结点的方法，它是从头结点开始，沿着指针域向后移动，直到找到第i个结点或者到达链表尾部为止。

/* 获取单链表中第i个元素,按序号查找，返回第i个结点的指针，如果不存在则返回NULL* @param L 链表头结点* @param i 元素位置* @return 第i个元素的指针，如果i不合法则返回NULL*/
LinkList GetElem(LinkList L, int i){if (i < 1) return NULL; //如果i不合法则返回NULLElemType j = 1; //j表示当前结点的位置LNode *p = L->next; //p指向第一个结点while (p && j<i){ //循环查找第i个结点p = p->next; //指向下一个结点j++; //位置加1}return p; //返回第i个结点的指针，如果不存在则返回NULL
}

单链表的按值查找

• 单链表的按值查找：单链表查找需要遍历链表，比较每个结点的数据域和给定的值是否相等，如果相等则返回该结点的位置，如果不相等则继续查找，直到遍历完整个链表或者找到匹配的结点为止。(这里其实有点不理解为啥都这样写，为啥都返回LinkList而不是具体的位置)

/* 单链表的按值查找,在单链表中查找元素e的位置* @param L 链表头结点* @param e 待查找的元素* @return 第一个值为e的结点的指针，如果不存在则返回NULL*/
LinkList LocateElem(LinkList L, int e){LNode *p = L->next; //p指向第一个结点while (p && p->data != e){ //循环查找值为e的结点p = p->next; //指向下一个结点}return p; //返回第一个值为e的结点的指针，如果不存在则返回NULL
}
------------------------------------------------------------------
/* 在单链表中查找元素e的位置* @param L 链表头结点* @param e 待查找的元素* @return 第一个值为e的结点的位置，如果不存在则返回0*/
ElemType LocateElem2(LinkList L, int e){ElemType j=1; //j表示当前结点的位置LNode *p = L->next; //p指向第一个结点while (p&&p->data!=e){ //循环查找值为e的结点p = p->next; //指向下一个结点j++; //位置加1}if (p)return j; //返回第一个值为e的结点的位置return -1; //如果不存在则返回-1
}

单链表的插入

• 单链表的插入：单链表插入需要找到插入位置的前驱结点，然后修改指针域，将新结点插入到前驱结点和后继结点之间。

/* 在单链表中插入元素e* @param L 链表头结点* @param i 插入位置* @param e 待插入的元素* @return 插入成功返回true，否则返回false*/
bool ListInsert(LinkList L, int i, int e){LinkList p = GetElem(L,i-1); //p指向第i-1个结点if (p==NULL)return false; //i-1个结点不存在LinkList q = (LinkList) malloc(sizeof(LNode)); //生成新结点q->data=e; //将新结点数据域赋值为eq->next=p->next; //新结点的指针域指向原第i个结点p->next=q;  //原第i-1个结点的指针域指向新结点return true; //插入成功
}

单链表的删除

• 单链表的删除：单链表删除需要找到删除位置的前驱结点，然后修改指针域，将待删除结点从链表中断开，并释放其空间。

/* 删除单链表L中第i个结点，并将删除的结点的数据域值赋给e* @param L 单链表L的头指针* @param i 待删除结点的位序* @param e 用e返回删除结点的数据域值* @return 删除成功返回true，否则返回false*/
bool ListDelete(LinkList L, int i, int &e){LinkList p = GetElem(L,i-1); //p指向第i-1个结点if(p == NULL || p->next == NULL) return false; //未找到第i-1个或第i个结点LNode *q = p->next; //q指向第i个结点e = q->data; //用e返回第i个结点的数据域值p->next = q->next; //原第i-1个结点的指针域指向原第i+1个结点free(q);//释放第i个结点空间return true; //删除成功
}

单链表的逆置

• 单链表的逆置：单链表逆置需要将原链表的结点从头到尾依次插入到一个新的空链表的头部，这样就可以实现原链表的逆序。

  

/* 反转单链表L* @param L 单链表L的头指针*/
void reverse(LinkList L) {if (isEmpty(L)) return; //如果链表为空，直接返回LinkList p = L->next; //p指向第一个结点L->next = NULL; //将头结点的指针域置为NULLwhile (p != NULL) {LinkList q = p->next; //q指向p的后继结点p->next = L->next; //将p插入到头结点之后L->next = p;p = q; //p指向下一个结点}
}

单链表的输出

• 单链表的输出：单链表输出是按照前后顺序打印出单链表中所有结点的值。

/* 打印单链表中的所有元素* @param L 链表头结点*/
void PrintList(LinkList L){LNode *p = L->next; //p指向第一个结点while(p != NULL){ //循环打印每个结点的数据域值，直到尾结点为止printf("%d\\t",p->data); //打印当前结点的数据域值p = p->next; //指向下一个结点}printf("\\n"); //打印完所有结点后换行
}

单链表的判空

单链表的判空：单链表判空是判断单链表是否为空，即头结点的指针域是否为NULL，如果为空，则返回true，否则返回false。

//判断单链表是否为空
bool isEmpty(LinkList L) {return L == NULL || L->next == NULL;
}

单链表的销毁

• 单链表的销毁：单链表销毁是释放所有结点所占用的内存空间，并将头结点置为NULL。

//销毁单链表
void destroy(LinkList &L) {//引用必须加while (L != NULL) {LNode *p = L; //p指向当前结点L = L->next; //L指向下一个结点free(p); //释放当前结点的内存}
}

main方法测试

int main() {LinkList L;InitList(L);//CreateList_Head(L);CreateList_Tail(L);PrintList(L);//LinkList M = GetElem(L,2);//printf("%d",M->data);//ElemType m = LocateElem2(L,4);ListInsert(L, 2, 99);//printf("%d",m);PrintList(L);ElemType e;ListDelete(L, 4, e);PrintList(L);reverse(L);PrintList(L);destroy(L);if (L == NULL || L->next == NULL) {printf("The list is empty or destroyed.\\n");} else {printf("The list is not empty or destroyed.\\n");}return 0;
}

双链表操作

双链表的定义

• 双链表的定义

  

//定义双链表结点
typedef struct DNode{int data; //数据域struct DNode *prior; //前驱指针struct DNode *next; //后继指针
}DNode, *DLinkList;

双链表的初始化

• 双链表的初始化

  

//初始化双链表
void InitDLinkList(DLinkList &L){L = (DLinkList) malloc(sizeof(DNode)); //分配头结点空间if(L == NULL) exit(-1); //分配失败退出L->prior = NULL; //头结点的前驱指针为空L->next = NULL; //头结点的后继指针为空
}

双链表的头插法

• 双链表的头插法

  

// 头插法创建双链表
void HeadInsert(DLinkList &L) {int x; // 输入的数据DLinkList s; // 新建的结点scanf("%d", &x); // 读入第一个数据while (x != 9999) { // 用9999作为结束标志s = (DLinkList) malloc(sizeof(DNode)); // 分配新结点空间if (s == NULL) exit(-1); // 分配失败退出s->data = x; // 将数据赋值给结点s->next = L->next; // 新结点的后继指针指向头结点的后继结点if (L->next != NULL) L->next->prior = s; // 如果头结点的后继结点不为空，将其前驱指针指向新结点L->next = s; // 头结点的后继指针指向新结点s->prior = L; // 新结点的前驱指针指向头结点scanf("%d", &x); // 继续输入下一个数据}
}

双链表的尾插法

• 双链表的尾插法

  

// 尾插法创建双链表
void TailInsert(DLinkList &L){int x; // 用于存储读入的数据DNode *s,*r; // s 用于指向新结点，r 用于指向尾结点r = L; // 初始时尾结点指向头结点scanf("%d", &x);//读入第一个数据while (x != 9999) { //用9999作为结束标志s = (DLinkList) malloc(sizeof(DNode)); //分配新结点空间if (s == NULL) exit(-1); //分配失败退出s->data = x; // 将数据存入新结点r->next = s; // 将新结点插入到链表尾部s->prior = r; // 将新结点的前驱指针指向尾结点r=s; // 将尾结点指向新结点scanf("%d", &x); // 读入下一个数据}r->next = NULL; // 将尾结点的后继指针赋空，表示链表的结束
}

双链表的按序号查找

• 双链表的按序号查找

// 获取双链表中第i个结点的指针
DLinkList GetElem(DLinkList L, int i){if (i < 1) return NULL; //如果i不合法则返回NULLint j = 1; //j表示当前结点的位置DNode *p = L->next; //p指向第一个结点while (p && j<i){ //循环查找第i个结点p = p->next; //指向下一个结点j++; //位置加1}return p; //返回第i个结点的指针，如果不存在则返回NULL
}

双链表的插入

• 双链表的插入

  

//双链表的插入
bool ListInsert(DLinkList L, int i, int e){DLinkList p = GetElem(L,i-1); //p指向第i-1个结点if (p==NULL)return false; //i-1个结点不存在DLinkList q = (DLinkList) malloc(sizeof(DNode)); //分配新结点空间q->data = e; //将e赋值给q的data域q->next =p->next; //将q的next指针指向p的next指针所指向的结点p->next->prior = q; //将p的next指针所指向的结点的prior指针指向qp->next = q; //将p的next指针指向qq->prior =p; //将q的prior指针指向preturn true; //返回true，表示插入成功
}

双链表的删除

• 双链表的删除

bool ListDelete(DLinkList L, int i, int &e){DLinkList p = GetElem(L,i-1); //p指向第i-1个结点if(p == NULL || p->next == NULL) return false; //未找到第i-1个或第i个结点DNode *q = p->next; //q指向第i个结点e = q->data; //用e返回第i个结点的数据域值p->next = q->next; //原第i-1个结点的指针域指向原第i+1个结点free(q);//释放第i个结点空间return true; //删除成功
}

双链表的判空

• 双链表的判空

//判断双链表是否为空，如果为空返回true，否则返回false
bool Empty(DLinkList L){return (L->next == NULL); //如果头结点的后继指针为空，说明双链表为空
}

双链表的打印

• 双链表的打印

/* 打印双链表中的所有元素* @param L 链表头结点*/
void PrintList(DLinkList L){if (Empty(L))printf("链表为空");DNode *p = L->next; //p指向第一个结点while(p != NULL){ //循环打印每个结点的数据域值，直到尾结点为止printf("%d\\t",p->data); //打印当前结点的数据域值p = p->next; //指向下一个结点}printf("\\n"); //打印完所有结点后换行
}

main方法测试

int main(){
DLinkList L;InitDLinkList(L);
//HeadInsert(L);PrintList(L);TailInsert(L);PrintList(L);//DLinkList T = GetElem(L,2);//printf("%d",T->data);if (ListInsert(L,2,100))PrintList(L);int e = 0;if (ListDelete(L,2,e))PrintList(L);printf("%d",e);//destroy(L);PrintList(L);return 0;
}

循环链表

循环单链表

typedef struct CSNode{int data; //数据域struct CSNode *next; //指针域
}CSNode, *CList;//初始化循环单链表
void InitCList(CList &L){L = (CSNode *)malloc(sizeof(CSNode)); //分配头结点空间if(L == NULL) exit(-1); //分配失败退出L->next = L; //头结点的指针域指向自己
}//判断循环单链表是否为空
bool Empty(CList L){return L->next == L; //头结点的指针域指向自己，说明链表为空
}//在循环单链表的第i个位置插入元素e
bool ListInsert(CList &L, int i, int e){if(i < 1) return false; //i值不合法CSNode *p = L; //p指向头结点int j = 0; //j为计数器while(p->next != L && j < i - 1){ //寻找第i-1个结点p = p->next;j++;}if(p == L && j !=0) return false; //i值不合法CSNode *s = (CSNode *)malloc(sizeof(CSNode)); //分配新结点空间if(s == NULL) return false; //分配失败s->data = e; //将数据赋值给新结点s->next = p->next; //新结点的指针域指向第i个结点p->next = s; //第i-1个结点的指针域指向新结点return true;
}//删除循环单链表的第i个位置的元素
bool ListDelete(CList &L, int i, int &e){if(i < 1 || L->next == L) return false; //i值不合法或循环链表为空CSNode *p = L; //p指向头结点int j = 0; //j为计数器while(p->next != L && j < i - 1){ //寻找第i-1个结点p = p->next;j++;}if(p->next == L || j > i - 1) return false; //i值不合法CSNode *q = p->next; //q指向第i个结点e = q->data; //将第i个结点的数据赋值给ep->next = q->next; //第i-1个结点的指针域指向第i+1个结点free(q); //释放被删除结点的空间return true;
}
//在循环单链表中查找值为e的结点，返回其位置
int LocateElem(CList L, int e){CSNode *p = L->next; //p指向第一个结点int i = 1; //i为计数器while(p != L && p->data != e){ //顺序查找p = p->next;i++;}if(p == L) return 0; //查找失败else return i; //查找成功，返回结点位置
}
//在循环单链表中按序号查找元素
int GetElem(CList L, int i){if(i < 1) return 0; //i值不合法CSNode *p = L->next; //p指向第一个结点int j = 1; //j为计数器while(p != L && j < i){ //顺序查找p = p->next;j++;}if(p == L) return 0; //查找失败else return p->data; //查找成功，返回结点数据
}
void PrintList(CList L){CSNode *p = L->next; //p指向第一个结点while(p != L){ //循环打印每个结点的数据域值，直到尾结点为止printf("%d\\t",p->data); //打印当前结点的数据域值p = p->next; //指向下一个结点}printf("\\n"); //打印完所有结点后换行
}
int main(){CList L;InitCList(L);ListInsert(L,1,55);ListInsert(L,1,66);ListInsert(L,1,77);PrintList(L);int e;ListDelete(L, 4, e);PrintList(L);}

循环双链表

typedef struct DCSNode{int data; //数据域struct DCSNode *prior; //前驱指针域struct DCSNode *next; //后继指针域
}DCSNode, *DLinkList;//初始化循环双链表
void InitDLinkList(DLinkList &L){L = (DCSNode *)malloc(sizeof(DCSNode)); //分配头结点空间if(L == NULL) exit(-1); //分配失败退出L->prior = L; //头结点的前驱指针域指向自己L->next = L; //头结点的后继指针域指向自己
}//判断循环双链表是否为空
bool Empty(DLinkList L){return L->next == L; //头结点的后继指针域指向自己，说明链表为空
}//在循环双链表的第i个位置插入元素e
bool ListInsert(DLinkList &L, int i, int e){if(i < 1) return false; //i值不合法DCSNode *p = L; //p指向头结点int j = 0; //j为计数器while(p->next != L && j < i - 1){ //寻找第i-1个结点p = p->next;j++;}if(p == L && j !=0) return false; //i值不合法DCSNode *s = (DCSNode *)malloc(sizeof(DCSNode)); //分配新结点空间if(s == NULL) return false; //分配失败s->data = e; //将数据赋值给新结点s->next = p->next; //新结点的后继指针域指向第i个结点p->next->prior = s; //第i个结点的前驱指针域指向新结点p->next = s; //第i-1个结点的后继指针域指向新结点s->prior = p; //新结点的前驱指针域指向第i-1个结点return true;
}//删除循环双链表的第i个位置的元素
bool ListDelete(DLinkList &L, int i, int &e){if(i < 1) return false; //i值不合法DCSNode *p = L; //p指向头结点int j = 0; //j为计数器while(p->next != L && j < i - 1){ //寻找第i-1个结点p = p->next;j++;}if(p->next == L || j > i - 1) return false; //i值不合法DCSNode *q = p->next; //q指向第i个结点e = q->data; //将第i个结点的数据赋值给ep->next = q->next; //第i-1个结点的后继指针域指向第i+1个结点q->next->prior = p; //第i+1个结点的前驱指针域指向第i-1个结点free(q); //释放被删除结点的空间return true;
}//在循环双链表中查找值为e的结点，返回其位置
int LocateElem(DLinkList L, int e){DCSNode *p = L->next; //p指向第一个结点int i = 1; //i为计数器while(p != L && p->data != e){ //顺序查找p = p->next;i++;}if(p == L) return 0; //查找失败else return i; //查找成功，返回结点位置
}//在循环双链表中按序号查找元素
int GetElem(DLinkList L, int i){if(i < 1) return 0; //i值不合法DCSNode *p = L->next; //p指向第一个结点int j = 1; //j为计数器while(p != L && j < i){ //顺序查找p = p->next;j++;}if(p == L) return 0; //查找失败else return p->data; //查找成功，返回结点数据
}
void PrintList(DLinkList L){DCSNode *p = L->next; //p指向第一个结点while(p != L){ //循环打印每个结点的数据域值，直到尾结点为止printf("%d\\t",p->data); //打印当前结点的数据域值p = p->next; //指向下一个结点}printf("\\n"); //打印完所有结点后换行
}
int main(){DLinkList L;InitDLinkList(L);ListInsert(L,1,55);ListInsert(L,1,66);ListInsert(L,1,77);ListInsert(L,1,88);PrintList(L);int e;ListDelete(L,1,e);PrintList(L);ListDelete(L,4,e);PrintList(L);}

稀疏多项式

一元稀疏多项式是指多项式的指数最大的一项的指数远远大于多项式的项数，且多项式中有很多零系数的项。为了节省空间，可以用链表来存储一元稀疏多项式，每个结点包含系数、指数和指针域。对于多项式的运算，可以按照指数的大小顺序合并两个链表，对于指数相同的项，进行系数的加减运算，对于指数不同的项，直接插入到结果链表中。

//
// Created by lenovo on 2023/4/15.
//
//定义结点结构体
#include <cstdio>
#include <cstdlib>
typedef struct Node {float coef; //系数int expn; //指数struct Node *next; //指针域
} Node, *PolyList;//初始化链表
void InitList(PolyList &L) {L = (Node *)malloc(sizeof(Node)); //分配头结点空间L->next = NULL; //头结点指针域置空
}//创建链表
void CreateList(PolyList &L, int n) {PolyList s, pre, q;for (int i = 1; i <= n; i++) { //依次输入n个非零项s = (Node *)malloc(sizeof(Node)); //分配新结点空间scanf("%f%d", &s->coef, &s->expn); //输入系数和指数pre = L; //pre用于保存q的前驱，初值为头结点q = L->next; //q初始化指向首元结点while (q && q->expn > s->expn) { //通过比较指数找到第一个小于输入项指数的项*qpre = q;q = q->next;}s->next = q; //将输入项s插入到q和其前驱结点pre之间pre->next = s;}
}//输出链表
void PrintList(PolyList L) {PolyList p = L->next; //p指向首元结点int flag = 0; //设置标志位，用于判断是否输出加号if (!p) { //如果链表为空，输出0printf("0\\n");return;}while (p) { //遍历链表，按格式输出每一项if (!flag) { //如果是第一项，不输出加号flag = 1;} else { //如果不是第一项，输出加号printf("+");}printf("%.1fx^%d", p->coef, p->expn); //输出系数和指数p = p->next; //p指向下一个结点}printf("\\n");
}//多项式相加
PolyList AddPoly(PolyList pa, PolyList pb) {PolyList p1, p2, p3, r, t;float sum;p1 = pa->next; //p1,p2初值指向首元结点p2 = pb->next;r = (Node *)malloc(sizeof(Node)); //创建一个新的头结点r->next = NULL;p3 = r; //p3指向和多项式当前结点，初值为rwhile (p1 && p2) { //当两个链表都不为空时，进行比较和合并操作if (p1->expn == p2->expn) { //如果两个结点的指数相同sum = p1->coef + p2->coef; //计算两个结点的系数之和if (sum != 0) { //如果系数之和不为0t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = sum; //将系数之和赋值给tt->expn = p1->expn; //将指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向t}p1 = p1->next; //p1,p2指向下一个结点p2 = p2->next;} else if (p1->expn > p2->expn) { //如果p1的指数大于p2的指数，将p1复制一份链在p3之后t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = p1->coef; //将p1的系数赋值给tt->expn = p1->expn; //将p1的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp1 = p1->next; //p1指向下一个结点} else { //如果p2的指数大于p1的指数，将p2复制一份链在p3之后t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = p2->coef; //将p2的系数赋值给tt->expn = p2->expn; //将p2的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp2 = p2->next; //p2指向下一个结点}}if (p1) { //如果pa还有剩余段，复制一份插入到新链表中while (p1) {t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = p1->coef; //将p1的系数赋值给tt->expn = p1->expn; //将p1的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp1 = p1->next; //p1指向下一个结点}}if (p2) { //如果pb还有剩余段，复制一份插入到新链表中，并改变系数符号while (p2) {t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = -p2->coef; //将p2的系数取反赋值给tt->expn = p2->expn; //将p2的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp2 = p2->next; //p2指向下一个结点}}return r; //返回新链表的头结点
}
//多项式相减
PolyList SubPoly(PolyList pa, PolyList pb) {PolyList p1, p2, p3, r, t;float diff;p1 = pa->next; //p1,p2初值指向首元结点p2 = pb->next;r = (Node *)malloc(sizeof(Node)); //创建一个新的头结点r->next = NULL;p3 = r; //p3指向差多项式当前结点，初值为rwhile (p1 && p2) { //当两个链表都不为空时，进行比较和合并操作if (p1->expn == p2->expn) { //如果两个结点的指数相同diff = p1->coef - p2->coef; //计算两个结点的系数之差if (diff != 0) { //如果系数之差不为0t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = diff; //将系数之差赋值给tt->expn = p1->expn; //将指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向t}p1 = p1->next; //p1,p2指向下一个结点p2 = p2->next;} else if (p1->expn > p2->expn) { //如果p1的指数大于p2的指数，将p1复制一份链在p3之后t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = p1->coef; //将p1的系数赋值给tt->expn = p1->expn; //将p1的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp1 = p1->next; //p1指向下一个结点} else { //如果p2的指数大于p1的指数，将-p2复制一份链在p3之后t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = -p2->coef; //改变p2的系数符号t->expn = p2->expn; //将p2的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp2 = p2->next; //p2指向下一个结点}}if (p1) { //如果pa还有剩余段，复制一份插入到新链表中while (p1) {t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = p1->coef; //将p1的系数赋值给tt->expn = p1->expn; //将p1的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp1 = p1->next; //p1指向下一个结点}}if (p2) { //如果pb还有剩余段，复制一份插入到新链表中，并改变系数符号while (p2) {t = (Node *)malloc(sizeof(Node)); //创建一个新的结点t->coef = -p2->coef; //将p2的系数取反赋值给tt->expn = p2->expn; //将p2的指数赋值给tt->next = NULL;p3->next = t; //将t链在p3之后p3 = t; //p3指向tp2 = p2->next; //p2指向下一个结点}}return r; //返回新链表的头结点
}//主函数
int main() {PolyList a, b, c,d; //定义三个多项式的链表InitList(a); //初始化a链表InitList(b); //初始化b链表int n1, n2; //定义两个多项式的项数printf("请输入第一个多项式的项数：\\n");scanf("%d", &n1); //输入第一个多项式的项数printf("请输入第一个多项式的系数和指数：\\n");CreateList(a, n1); //创建第一个多项式的链表printf("请输入第二个多项式的项数：\\n");scanf("%d", &n2); //输入第二个多项式的项数printf("请输入第二个多项式的系数和指数：\\n");CreateList(b, n2); //创建第二个多项式的链表printf("两个多项式相加的结果为：\\n");c = AddPoly(a, b); //进行多项式相减运算，返回结果链表的头结点PrintList(c); //输出结果多项式printf("两个多项式相减的结果为：\\n");d = SubPoly(a, b); //进行多项式相减运算，返回结果链表的头结点PrintList(d); //输出结果多项式return 0;
}/*//多项式相加
void AddPoly(PolyList &pa, PolyList &pb) {PolyList p1, p2, p3, r;float sum;p1 = pa->next; //p1,p2初值指向首元结点p2 = pb->next;p3 = pa; //p3指向和多项式当前结点，初值为pawhile (p1 && p2) { //当两个链表都不为空时，进行比较和合并操作if (p1->expn == p2->expn) { //如果两个结点的指数相同sum = p1->coef + p2->coef; //计算两个结点的系数之和if (sum != 0) { //如果系数之和不为0p1->coef = sum; //修改pa为两系数的和p3->next = p1; //将修改后的pa当前结点链在p3之后p3 = p1; //p3指向p1p1 = p1->next; //p1指向下一个结点r = p2; //r指向p2p2 = p2->next; //p2指向下一个结点free(r); //释放r所指的结点空间} else { //如果系数之和为0，删除两个结点r = p1; //r指向p1p1 = p1->next; //p1指向下一个结点free(r); //释放r所指的结点空间r = p2; //r指向p2p2 = p2->next; //p2指向下一个结点free(r); //释放r所指的结点空间}} else if (p1->expn > p2->expn) { //如果p1的指数大于p2的指数，将p1链在p3之后p3->next = p1;p3 = p1;p1 = p1->next;} else { //如果p2的指数大于p1的指数，将p2链在p3之后p3->next = p2;p3 = p2;p2 = p2->next;}}p3->next = p1 ? p1 : p2; //插入非空多项式的剩余段free(pb); //释放pb的头结点空间
}
//多项式相减
void SubPoly(PolyList &pa, PolyList &pb) {PolyList p1, p2, p3, r;float diff;p1 = pa->next; //p1,p2初值指向首元结点p2 = pb->next;p3 = pa; //p3指向差多项式当前结点，初值为pawhile (p1 && p2) { //当两个链表都不为空时，进行比较和合并操作if (p1->expn == p2->expn) { //如果两个结点的指数相同diff = p1->coef - p2->coef; //计算两个结点的系数之差if (diff != 0) { //如果系数之差不为0p1->coef = diff; //修改pa为两系数的差p3->next = p1; //将修改后的pa当前结点链在p3之后p3 = p1; //p3指向p1p1 = p1->next; //p1指向下一个结点r = p2; //r指向p2p2 = p2->next; //p2指向下一个结点free(r); //释放r所指的结点空间} else { //如果系数之差为0，删除两个结点r = p1; //r指向p1p1 = p1->next; //p1指向下一个结点free(r); //释放r所指的结点空间r = p2; //r指向p2p2 = p2->next; //p2指向下一个结点free(r); //释放r所指的结点空间}} else if (p1->expn > p2->expn) { //如果p1的指数大于p2的指数，将p1链在p3之后p3->next = p1;p3 = p1;p1 = p1->next;} else { //如果p2的指数大于p1的指数，将-p2链在p3之后p2->coef = -p2->coef; //改变p2的系数符号p3->next = p2;p3 = p2;p2 = p2->next;}}if (p3->next = p1) { //插入非空多项式的剩余段p3->next = p1;} else {p3->next = p2;while (p2) { //第二段连上要变成负的p2->coef = -p2->coef; //改变每个结点的系数符号p2 = p2->next;}}free(pb); //释放pb的头结点空间
}
//主函数
int main() {PolyList a, b; //定义两个多项式的链表InitList(a); //初始化a链表InitList(b); //初始化b链表int n1, n2; //定义两个多项式的项数printf("请输入第一个多项式的项数：\\n");scanf("%d", &n1); //输入第一个多项式的项数printf("请输入第一个多项式的系数和指数：\\n");CreateList(a, n1); //创建第一个多项式的链表printf("请输入第二个多项式的项数：\\n");scanf("%d", &n2); //输入第二个多项式的项数printf("请输入第二个多项式的系数和指数：\\n");CreateList(b, n2); //创建第二个多项式的链表printf("两个多项式相加的结果为：\\n");AddPoly(a, b); //进行多项式相加运算PrintList(a); //输出结果多项式return 0;
}*/

云服务器