4：删除链表数据
struct student* destory(struct student* head, int del) //头节点和待删除数据 { struct student* p, * before_p; //建立中间节点和中间节点之前的一个节点 if (head == NULL) //头指针为空 { cout << "链表为空！！" << endl; return (head); } p = head; while ((p->age != del) && (p->next != NULL))//判断是否遇到了要删除的数或者是否达到了链表尾 { //1:达到链表尾 2：遇到了要删除的数据 before_p = p; //记录p(要删除数据地址)的前一个节点 p = p->next; //如果不是要删除的数据则继续遍历，如果while停止，那么p当前的位置就是要删除的数据的位置 }//当while结束时，此时p指向的地址就是要删除的数据的地址 if (p->age == del)//遇到了要删除的数据 { if (p == head)//如果数据是头节点 head = p->next; //让指针直接指向下一个地址 1：下一个地址是空 那么直接指向的是null else //2：下一个地址存在，那么直接指向下一个数据地址 before_p->next = p->next; //before_p->next==p p要删除 那么直接让before_p=p->next,就可以做到p直接消失 cout << "要删除的学生的年龄是" << del << endl; n = n - 1; //节点数量减一 if (n == 0) { cout << "目前已经没有学生消息！！"<<endl; } } else //已经达到了链表尾 cout << "链表中没有要删除的数据！！" << endl; return (head); }
5：插入数据
struct student* insert_s(struct student* head, struct student* newdata)//排序插入 { struct student* p; if (head == NULL)//头指针为空，没有数据存在，那么插入的数据就是头指针 { head = newdata; //newdata就是头指针，并且头指针的下一个节点为空 head->next = NULL; return (head); } if (newdata->age < head->age)//插入的数据小于头指针指向的数据，那么直接把这个数据作为都指针 { newdata->next = head; //让原先头指针指向newdata的下一个节点 head = newdata; //将newdata作为头指针 return (head); //这一步操作完成后，原先newdata和head的地址调换 } p = head;//不是以上两种情况，说明数据在中间 while ((p->next != NULL) && (p->next->age < newdata->age))//while停下时达到尾指针或p->next->age >= newdata->age p = p->next;//后面这个东西是由于上面已经判断过头指针数据与新加数据的大小了，因此直接指向下一个去比较 //当停下时 p->next->age>=newdata->age,因此要将newdata代替p->next，且newdata->next=p->next(原先指向的) newdata->next = p->next; //这一步便可以理解了 p->next = newdata; return (head); } //代码完
6：缺点
由于链表的特性，导致每次需要访问想要的元素时，需要遍历整个链表（这是由于链表创建时头指针是确定的，但是接下来的每一个位置都和数组不一样，他们是随机存在的，因此不确定下一个地址的位置，只能靠头指针向下遍历），那么运气好时在第一个位置时的时间复杂度为O(1),最后一个位置的时间复杂度O(n),那么可以得到平均的时间复杂度O(n).
7：优点
由上述代码可以发现，如果要插入或者删除数据，那么只需要将对应位置前和后的一个指针所指向的位置改变就可以了，那么只需要操作一次，时间复杂度为O(1)。
三、链式存储结构（方法2伪代码）
1：结构体创建
typedef int ElemType; typedef struct Node { ElemType data; struct Node* next; }Node; typedef struct Node* LinkList;
2：创建链表
void CreatList(LinkList* L, int n)//创建的节点个数 { srand(time(0)); LinkList p,r; *L = (LinkList)malloc(sizeof(Node)); //(*L)->next = NULL; (*L) = r; for (int i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; //(*L)->next = p; r->next = p; //(*L) = p; r = p; } (*L)->next = NULL; }
3：删除链表
void CreatList(LinkList* L, int n)//创建的节点个数 { srand(time(0)); LinkList p,r; *L = (LinkList)malloc(sizeof(Node)); //(*L)->next = NULL; (*L) = r; for (int i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; //(*L)->next = p; r->next = p; //(*L) = p; r = p; } (*L)->next = NULL; }
4：获取元素
Status GetElem(LinkList L,int i,ElemType *e)//找到第i个元素，赋给e后返回 { int k= 1; LinkList p; p = L->next; //p为指向第一个数据的指针 while ((k < i) && p) //停下时k=i或p为空 { p = p->next; ++k; } if (!p||k>i) return ERROR; *e = L->data; return OK; }
5：插入元素
Status InsertElem(LinkList * L, int i, ElemType e) { int k = 1; LinkList p, s; p = *L; while (p && (k < i))//停下时p为空或k=i { p = p->next; ++k; } if (!p || i < k) return ERROR; s = (LinkList)malloc(sizeof(Node)); s->next=p->next; p->next = s; s->data = e; return OK; }
6：删除元素
Status DeleteList(LinkList* L, int i, ElemType* e) { int k = 1; LinkList p, s; p = *L; while (p->next && k < i) { s = p; //p为要删除的，s为要删除的前一个 p=p->next; ++k; } if (!s->next || k > i) //s不是链表尾 return ERROR; s->next = p->next; return OK; }
四、线性表子系统
通过上面的学习，我们可以知道其实只需要通过整合上面的代码并且加上菜单进行选择就可以实现题目的要求，因此直接奉上代码
#include<algo.h> typedef int ElemType; typedef struct { ElemType add[MAXSIZE]; //数组基地址类型 int length; //线性表长度 1,2,3...元素个数 }List; List* InitElem() { List *head; head = (List*)malloc(sizeof(List)); head->length = 0; do { cout << "输入数据(按0退出，0不会被保存入链表)" << endl; cin >> head->add[head->length]; head->length++; } while (head->length < MAXSIZE && head->add[head->length-1] != 0.0); head->add[head->length-1]=NULL; return head; } Status ShowElem(List L) { int i = 0; if (L.length == 0) { cout << "当前链表没有数据" << endl; return ERROR; } while(1) { if (i < L.length-1) cout <<"第"<<i<<"个数据是" << L.add[i++] << endl; else break; } return OK; } Status FreeElem(List* L)//清空线性表 { free(L); return OK; } Status EmptyElem(List L)//判断线性表是否为空 { if (&L == NULL) return TRUE ; else return FALSE; } int LengthElem(List L) //获得链表长度 { return L.length-1; } int LocationElem(List L, ElemType e) //查找 返回要找的元素在链表中的位置 { int k = 0; while (k<L.length) { if (e == L.add[k]) return k+1; else k++; } cout << "没有找到！" << endl; return ERROR; } Status GetElem(List L, int i, ElemType *e)//获得顺序链表里第i个数据并返回 { if (i<1 || i>L.length)//元素不存在于链表中 { cout << "i的值不合理！" << endl; return ERROR; } else if (L.length == 0) { cout << "链表为空！" << endl; return ERROR; } else { *e = L.add[i - 1]; //成功后e指向的地址的值就是第i个数据的值 cout << "成功！" << endl; } return OK; } Status InsertElem(List *L, int i, ElemType e)//在L中的第i个位置插入新元素e { if (i > L->length + 1 || i < 1)//判断所插入的位置是否合理 { cout << "i的值不合理！" << endl; return ERROR; } if (L->length == MAXSIZE)//判断是否超出了数组容量 { cout << "数组已满！" << endl; return ERROR; } if (i <= L->length) //要在中间插入，那么移动的次数应该是length-i+1 { cout << "数据移动！" << endl; cout << "在第" << i << "个位置插入数据" << e << endl; for (int k=L->length-1;k>=i-1;k--)//插入操作，从后向前遍历 L->add[k+1] = L->add[k]; //这是由于插入后数组扩容，那么需要将插入位置之后的所有元素 } //先向后移动一个位置，腾出空位给要插入的元素，从前也可以，但是需要创建临时变量 L->add[i - 1] = e; //将要插入的数据插入数据 L->length++;//数组元素增加 return OK; } Status DelElem(List *L,int i,ElemType* e)//移动次数length-i { int k; if (L->length == 0) //链表长度为0，说明不存在元素 { cout << "链表为空！！" << endl; return ERROR; } if (i > L->length || i < 1)//要删除的位置不合理 { cout << "i的值不对 " << endl; return ERROR; } *e = L->add[i - 1]; //读取要删除的元素的值 cout <<"要删除的值是"<< *e << endl; if (i < L->length) { for (k = i; k < L->length; k++) { //删除元素是后面的元素向前移动，那么从前往后遍历可以将后面的元素一个一个的向前覆盖 L->add[k - 1] = L->add[k]; } } L->length--; //长度减一 return OK; } int main() { int choose; List* head = (List*)malloc(sizeof(List)); head->length = 0; ElemType e; cout << "***************"<< endl; cout << "*1 ……建表 *" << endl; cout << "*2 ……插入 *" << endl; cout << "*3 ……删除 *" << endl; cout << "*4 ……显示 *" << endl; cout << "*5 ……查找 *" << endl; cout << "*6 ……求表长 *" << endl; cout << "*0 ……返回 *"<< endl; cout << "***************" << endl; while (1) { cout << "请选择功能" << endl; scanf("%d", &choose); switch (choose) { case 1: { head = InitElem(); cout << "创建成功" << endl; break; } case 2: { int location,data; cout << "输入要插入数据的位置和数据的值" << endl; cin >> location>>data; int sucess = InsertElem(head, location, data); if (sucess == 1) cout << "插入成功" << endl; else cout << "插入失败" << endl; break; } case 3: { int location; cout << "输入要删除数据的位置" << endl; cin >> location; int sucess = DelElem(head, location, &e); if (sucess == 1) cout << "删除成功" << endl; else cout << "删除失败" << endl; break; } case 4: { ShowElem(*head); break; } case 5: { int find; cout << "输入你要查找的数据" << endl; cin >> find; LocationElem(*head, find); break; } case 6: { int length; length = LengthElem(*head); cout << "链表长度为" << length << endl; break; } case 0: { cout << "程序结束" << endl; system("pause"); exit(0); //return 0; } default: break; } } }
总结
在不需要经常插入时，顺序结构效率更高，而在需要经常插入数据时，链式存储结构效率更高。
