|
发表于 2022-11-2 19:51:23
|
显示全部楼层
- #include <iostream>
- #include <ctype.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <math.h>
- #include <time.h>
- using namespace std;
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- #define MAXSIZE 20
- typedef int Status;
- typedef int ElemType;
- typedef struct Node {
- ElemType data;
- struct Node *next;
- } Node;
- typedef struct Node *LinkList;
- Status InitList(LinkList *L);
- Status DestroyList(LinkList *L);
- Status ClearList(LinkList *L);
- Status ListInsert(LinkList *L, int i, ElemType e);
- Status ListDelete(LinkList *L, int i, ElemType *e);
- Status ListEmpty(LinkList L);
- int ListLength(LinkList L);
- Status GetElem(LinkList L, int i, ElemType *e);
- int LocateElem(LinkList L, ElemType e);
- Node *LocateElem2(LinkList L, ElemType e);
- Status ListTraverse(LinkList L);
- Status InitList(LinkList *L) {
- *L = new Node;
- if(!(*L)) {
- return ERROR;
- }
- (*L)->next = NULL;
- return OK;
- }
- // 函数也成对编写,写了初始化函数,下一个就写销毁函数
- // 不然你很容易就把这个函数忘了
- // 不然你打算什么时候写这个函数?
- // 写完了其他的所有函数然后再写这个函数?
- // 写到中途突然想起来了,然后再补上这个函数?
- //
- // 还有,你既然写了这些函数,为什么不用呢?
- // 销毁链表的这个函数就是把整个链表删除掉么
- // 你直接把链表清空了,然后释放头结点不就可以了
- // 像你这样写,每一个函数都直接操作底层结构
- // 不仅代码不好理解而且还非常容易出错
- // 出了错,要调试程序也很不好调试
- Status DestroyList(LinkList *L) {
- /*
- LinkList p;
- while(*L) {
- p = *L;
- *L = (*L)->next;
- delete p;
- }
- */
- ClearList(L);
- delete *L;
- *L = NULL;
- return OK;
- }
- // 清空链表也不需要直接操作底层结构吧
- // 不仅代码不好理解而且还非常容易出错
- // 调试的时候也是个麻烦
- // 一直调用删除结点的函数,删除第0个结点,直到链表为空
- Status ClearList(LinkList *L) {
- /*
- LinkList p, q;
- p = (*L)->next;
- while(p) {
- q = p->next;
- //free(p); // 这是什么操作?
- // 用 new 关键字申请内存
- // 然后用 free 函数释放内存?
- delete p;
- p = q;
- }
- (*L)->next = NULL;
- */
- ElemType e;
- while(!ListEmpty(*L)) ListDelete(L, 1, &e); // 你这从1开始数的吧,我们编程中从0开始数
- return OK;
- }
- Status ListInsert(LinkList *L, int i, ElemType e) {
- int j;
- LinkList p, s;
- p = *L;
- j = 1;
- while(p && j < i) {
- p = p->next;
- ++j;
- }
- if(!p || j > i) {
- return ERROR;
- }
- s = new Node;
- s->data = e;
- s->next = p->next;
- p->next = s;
- return OK;
- }
- Status ListDelete(LinkList *L, int i, ElemType *e) {
- int j;
- LinkList p, q;
- p = *L;
- j = 1;
- while(p->next && j < i) {
- p = p->next;
- ++j;
- }
- if(!(p->next) || j > i) {
- return ERROR;
- }
- q = p->next;
- p->next = q->next;
- *e = q->data;
- delete(q);
- return OK;
- }
- Status ListEmpty(LinkList L) {
- if(L->next) {
- return FALSE;
- } else {
- return TRUE;
- }
- }
- int ListLength(LinkList L) {
- int i = 0;
- LinkList p = L->next;
- while(p) {
- i++;
- p = p->next;
- }
- return i;
- }
- Status GetElem(LinkList L, int i, ElemType *e) {
- int j;
- LinkList p;
- p = L->next;
- j = 1;
- while(p && j < i) {
- p = p->next;
- j++;
- }
- if(!p || j > i) {
- return ERROR;
- }
- *e = p->data;
- return OK;
- }
- int LocateElem(LinkList L, ElemType e) {
- int i = 0;
- LinkList p = L->next;
- while(p) {
- i++;
- if(p->data == e) {
- return i;
- }
- p = p->next;
- }
- return 0;
- }
- Node *LocateElem2(LinkList L, ElemType e) {
- LinkList p = L->next;
- // while (p && p->data!=e)
- //{
- // p = p->next;
- // }
- // return p;
- while(p) {
- /*
- // 如果不是e的话,换下一个
- // 如果是e的话,怎么办?
- if(p->data != e) {
- p = p->next;
- }
- */
- if(p->data != e) {
- p = p->next;
- } else break; // 退出循环对不对?
- }
- return p;
- }
- Status visit(ElemType c) {
- cout << c << " ";
- return OK;
- }
- Status ListTraverse(LinkList L) {
- /*
- LinkList p = L->next;
- while(p) {
- visit(p->data);
- p = p->next;
- }
- cout << endl;
- */
- // 你这个求链表长度的函数应该把长度信息保存下来的
- // 这样每一次调用这个函数都遍历一遍链表
- // 虽然说可读性很重要,但是保证了可读性以后
- // 效率问题你也不能不管,除非他俩冲突了
- // 在顶层不要直接操作底层结构
- // 还是那句话
- // 不仅代码不好理解而且还非常容易出错
- // 调试的时候也是个麻烦
- // 你说把代码写成下面这样
- // 不好理解?不好调试?容易出错?
- for(int i = 1; i <= ListLength(L); ++i) {
- ElemType e;
- GetElem(L, i, &e);
- visit(e);
- }
- return OK;
- }
- void CreateListHead(LinkList *L, int n) {
- LinkList p;
- int i;
- //srand(time(0)); // 这个不能放在这里
- *L = new Node;
- (*L)->next = NULL;
- for(i = 0; i < n; i++) {
- p = new Node;
- p->data = rand() % 100 + 1;
- p->next = (*L)->next;
- (*L)->next = p;
- }
- }
- void CreateListTail(LinkList *L, int n) {
- LinkList p, r;
- int i;
- //srand(time(0));
- *L = new Node;
- r = *L;
- for(i = 0; i < n; i++) {
- p = new Node;
- p->data = rand() % 100 + 1;
- r->next = p;
- r = p;
- }
- r->next = NULL;
- }
- int main() {
- srand(time(NULL)); // 这个函数调用应该放在这里
- LinkList L;
- ElemType e;
- Status i;
- int j, k;
- i = InitList(&L);
- cout << "初始化L后:ListLength(L)=" << ListLength(L) << endl;
- for(j = 1; j <= 5; j++) {
- i = ListInsert(&L, 1, j);
- }
- cout << "在L的表头依次插入1~5后:L.date=" << endl;
- ListTraverse(L);
- cout << "ListLength(L)=" << ListLength(L) << endl;
- i = ListEmpty(L);
- cout << "L是否空:(1:是 0:否)" << i << endl;
- i = ClearList(&L);
- cout << "清空L后:ListLength(L)=" << ListLength(L) << endl;
- i = ListEmpty(L);
- cout << "L是否空:(1:是 0:否)" << i << endl;
- for(j = 1; j <= 10; j++) {
- ListInsert(&L, j, j);
- }
- cout << "在L的表尾依次插入1~10后:L.date=";
- ListTraverse(L);
- cout << "ListLength(L)=" << ListLength(L) << endl;
- ListInsert(&L, 1, 0);
- cout << "在L的表头插入0后:L.date=";
- ListTraverse(L);
- cout << "ListLength(L)=" << ListLength(L) << endl;
- GetElem(L, 5, &e);
- cout << "第5个元素的值为:" << e << endl;
- for(j = 3; j <= 4; j++) {
- k = LocateElem(L, j);
- if(k) {
- cout << "第" << k << "个元素的值为:" << j << endl;
- } else {
- cout << "没有值为" << j << "的元素" << endl;
- }
- }
- k = ListLength(L);
- for(j = k + 1; j >= k; j--) {
- i = ListDelete(&L, j, &e);
- if(i == ERROR) {
- cout << "删除第" << j << "个元素失败" << endl;
- } else {
- cout << "删除第" << j << "个元素的值:" << e << endl;
- }
- }
- cout << "依次输出L的元素:";
- ListTraverse(L);
- j = 5;
- ListDelete(&L, j, &e);
- cout << "删除第" << j << "个元素的值为:" << e << endl;
- cout << "依次输出L的元素:";
- ListTraverse(L);
- i = ClearList(&L);
- cout << "\n清空L后:ListLength(L)=" << ListLength(L) << endl;
- DestroyList(&L);
- CreateListHead(&L, 20);
- cout << "整体创建L的元素(头插法)";
- ListTraverse(L);
- i = ClearList(&L);
- cout << "\n删除L后:ListLength(L)=" << ListLength(L) << endl;
- DestroyList(&L);
- CreateListTail(&L, 20);
- cout << "整体创建L的元素(尾插法):";
- ListTraverse(L);
- i = ClearList(&L);
- cout << "\n删除L后:ListLength(L)=" << ListLength(L) << endl;
- DestroyList(&L);
- //system("pause"); // 不是所有的环境都支持这个命令,尽量还是不要用
- return 0;
- }
复制代码 |
|