数据结构顺序表—链表的创建

链表：

链式前项星.¹

• 1. 该方法实现链表最重要的是使用数组模拟指针，从而达到各个节点相连接的目的。

const int N=Maxsize; //链表的创建 //h 表示头结点 ；e[N] 用来储存链表中各个节点的值；idx 用来方便插入节点 int h,e[N],ne[N],idx; 

• 2. 相比于结构体实现的单链表而言，该种方式链表的初始化较为简单

讯享网h=-1; idx=0; 

• 3. 链表的插入操作方式同样可以按照单链表方式来理解

void insert(int val) { e[idx]=a,ne[idx]=h,h=idx++; } 

• 4. 删除操作 删除 idx 后的一个节点

讯享网void del(int idx) { ne[idx]=ne[ne[idx]]; } 

单链表²

下面重点说一下单链表的结构体实现方式

• 1. 首先创建节点

typedef struct Link { int elem; struct Link *next; }link; 

• 2. 初始化，这里在初始化的过程中同时插入n个节点(头插法)

link * initLink_head(int n) { link * p = (link*)malloc(sizeof(link));//创建一个头结点 link * temp = p;//声明一个指针指向头结点，用于遍历链表 //生成链表 temp->next=NULL; for (int i = 1; i < n+1; i++) { link *a = (link*)malloc(sizeof(link)); a->elem = i; a->next = temp->next; temp->next = a; } return p; } 

• 3. 插入元素

link * insertElem(link * p, int elem, int add) { link * temp = p;//创建临时结点temp //首先找到要插入位置的上一个结点 for (int i = 1; i < add; i++) { temp = temp->next; if (temp == NULL) { printf("插入位置无效\n"); return p; } } //创建插入结点c link * c = (link*)malloc(sizeof(link)); c->elem = elem; //向链表中插入结点 c->next = temp->next; temp->next = c; return p; } 

• 4. 删除元素

link * delElem(link * p, int add) { link * temp = p; //遍历到被删除结点的上一个结点 for (int i = 1; i < add; i++) { temp = temp->next; if (temp->next == NULL) { printf("没有该结点\n"); return p; } } link * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失 temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域 free(del);//手动释放该结点，防止内存泄漏 return p; } 

• 5. 元素的查找

int selectElem(link * p, int elem) { link * t = p; int i = 1; while (t->next) { t = t->next; if (t->elem == elem) { return i; } i++; } return -1; } 

• 6. 这里提供一种链表的排序实现（冒泡排序 $O(n^2)$）,由于链表只能从后向前遍历，不能任意
     取出节点中的元素进行比较，所以，使用快排或者归并排序很难实现
     (主要是博主是蒟蒻，不会实现//大哭)

void sort(link* p) { int size=0; link* head=p; while(p->next) { p=p->next; size++; } for(int i=size;i>1;i--) { //循环size-1次，每次可以选出一个最大的值 link* l=head->next; for(int j=1;j<i;j++) { if(l->elem > l->next->elem) { int tem=l->elem; l->elem=l->next->elem; l->next->elem=tem; } l=l->next; } } } 

• 7. 链表的遍历

void display(link *p) { link* temp = p;//将temp指针重新指向头结点 //只要temp指针指向的结点的next不是Null，就执行输出语句。 while (temp->next) { temp = temp->next; p printf("\n"); } 

下面给出完整代码

#include <iostream>　　　　//增+删+改+查+初始化+输出 #include <stdlib.h> typedef struct Link { int elem; struct Link *next; }link; link * initLink(); //链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置 link * insertElem(link * p, int elem, int add); //删除结点的函数，p代表操作链表，add代表删除节点的位置 link * delElem(link * p, int add); //查找结点的函数，elem为目标结点的数据域的值 int selectElem(link * p, int elem); //更新结点的函数，newElem为新的数据域的值 link * initLink_head(int i); link *insertElem(link* p,int lenm,int add); link *amendElem(link * p, int add, int newElem); void display(link *p); void sort(link* p); //int main() { // //初始化链表（1，2，3，4） // printf("初始化链表为：\n"); // link *p = initLink_head(5); // display(p); // printf("在第4的位置插入元素5：\n"); // p = insertElem(p, 5, 4); // display(p); // printf("删除第三个位置的元素:\n"); // p = delElem(p, 3); // display(p); // printf("查找元素2的位置：\n"); // int address = selectElem(p, 2); // if (address == -1) { // printf("没有该元素"); // } // else { // printf("%d\n", address); // } // printf("更改第3的位置上的数据为7:\n"); // p = amendElem(p, 3, 7); // display(p); // sort( p); // display(p); // return 0; //} int main() { int cnt,n; printf("初始化链表为：\n"); printf("输入初始化节点的个数\n"); scanf("%d",&cnt); link *p = initLink_head(cnt); display(p); printf("输入 0 退出;\n输入 1 插入节点;\n输入 2 删除节点;\n输入 3 查找节点;\n输入 4 输出各个节点;\n输入 5 节点排序.\n"); printf("\t*\n"); scanf("%d",&n); while(n) { if(n==1) { int i,x; printf("在第i的位置插入元素x：\n"); printf("i="); scanf("%d",&i); puts(""); printf("x="); scanf("%d",&x); p = insertElem(p, x, i); } else if(n==2) { int i; printf("删除第i个位置的元素:\n"); printf("i="); scanf("%d",&i); p = delElem(p, i); } else if(n==3) { int i; printf("查找元素i的位置：\n"); printf("i="); scanf("%d",&i); int address = selectElem(p, 2); if (address == -1) { printf("没有该元素"); } } else if(n==4) { display(p); } else { sort(p); } printf("输入操作选项"); scanf("%d",&n); } return 0; } link * initLink() { link * p = (link*)malloc(sizeof(link));//创建一个头结点 link * temp = p;//声明一个指针指向头结点，用于遍历链表 //生成链表 for (int i = 1; i < 5; i++) { link *a = (link*)malloc(sizeof(link)); a->elem = i; a->next = NULL; temp->next = a; temp = temp->next; } return p; } link * initLink_head(int n) { link * p = (link*)malloc(sizeof(link));//创建一个头结点 link * temp = p;//声明一个指针指向头结点，用于遍历链表 //生成链表 temp->next=NULL; for (int i = 1; i < n+1; i++) { link *a = (link*)malloc(sizeof(link)); a->elem = i; a->next = temp->next; temp->next = a; } return p; } link * insertElem(link * p, int elem, int add) { link * temp = p;//创建临时结点temp //首先找到要插入位置的上一个结点 for (int i = 1; i < add; i++) { temp = temp->next; if (temp == NULL) { printf("插入位置无效\n"); return p; } } //创建插入结点c link * c = (link*)malloc(sizeof(link)); c->elem = elem; //向链表中插入结点 c->next = temp->next; temp->next = c; return p; } link * delElem(link * p, int add) { link * temp = p; //遍历到被删除结点的上一个结点 for (int i = 1; i < add; i++) { temp = temp->next; if (temp->next == NULL) { printf("没有该结点\n"); return p; } } link * del = temp->next;//单独设置一个指针指向被删除结点，以防丢失 temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域 free(del);//手动释放该结点，防止内存泄漏 return p; } int selectElem(link * p, int elem) { link * t = p; int i = 1; while (t->next) { t = t->next; if (t->elem == elem) { return i; } i++; } return -1; } link *amendElem(link * p, int add, int newElem) { link * temp = p; temp = temp->next;//tamp指向首元结点 //temp指向被删除结点 for (int i = 1; i < add; i++) { temp = temp->next; } temp->elem = newElem; return p; } void display(link *p) { link* temp = p;//将temp指针重新指向头结点 //只要temp指针指向的结点的next不是Null，就执行输出语句。 while (temp->next) { temp = temp->next; p printf("\n"); } // 冒泡排序 void sort(link* p) { int size=0; link* head=p; while(p->next) { p=p->next; size++; } for(int i=size;i>1;i--) { //循环size-1次，每次可以选出一个最大的值 link* l=head->next; for(int j=1;j<i;j++) { rintf("%d ", temp->elem); } if(l->elem > l->next->elem) { int tem=l->elem; l->elem=l->next->elem; l->next->elem=tem; } l=l->next; } } }