数据结构实验2.zip
资源内容介绍
数据结构实验2.zip #define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FLASE 0#include<stdio.h>#include<stdlib.h> #include<malloc.h> //用于内存分配typedef int Status; //int 类型的别名typedef int ElemType; //int 类型的别名typedef struct LNode {ElemType data; //数据域struct LNode* next; //指向下一个节点的指针} LNode,*LinkList; //LinkList 是指向链表节点的指针/*CreatLinkL1:创建带有头结点的单链表LinkList &L：指向链表的指针（使用引用传递，允许函数修改传入的指针）。int n：表示需要创建的链表元素数量。ElemType *E：是一个指向元素的指针，用于存储需要添加到链表中的数据。*/Status CreatLinkL1(LinkList &L,int n,ElemType *E) { //int i;LinkList p; //指向链表节点的指针 pL=(LinkList) malloc(sizeof(LNode)); //分配了一个新的节点内存空间，malloc(sizeof(LNode)) 分配了一个节点大小的内存，然后将其地址赋值给 L，即链表的头结点。if(!L) return ERROR; //检查分配内存是否成功，函数返回 ERROR，表示创建链表失败。L->next=NULL; //将头结点的 next 指针设置为 NULL，因为目前链表中没有其他节点。for(i=n-1; i>=0; --i){ //用循环逆向遍历数组 E 中的元素，准备创建链表节点if(!(p=(LinkList)malloc(sizeof(LNode)))) //分配新的节点内存空间return ERROR;p->data=E[i]; //将节点 p 的 data 域赋值为数组 E 中相应位置的元素值。 //*********************************----------1-------------p->next=L->next; //将节点 p 的 next 指向当前链表的第一个节点，即头结点 L 的 next 指针所指向的位置（在第一次循环时为 NULL）。//**************************************************-----------------2------------------L->next=p; //将新节点 p 插入到链表的头部，使头结点指向它，成为新的第一个节点。}return OK; //若所有节点创建成功，函数返回 OK，表示创建链表成功}/*链表创建函数，采用尾插法来建立带有头结点的单链表LinkList &L：指向链表的指针（使用引用传递，允许函数修改传入的指针）。int n：表示需要创建的链表元素数量。ElemType *E：是一个指向元素的指针，用于存储需要添加到链表中的数据。*/Status CreatLinkL2(LinkList &L,int n,ElemType *E) {//用表尾插入法建立带头结点的单链表int i;LinkList p,r; //声明两个指向链表节点的指针 p 和 r。L = (LinkList)malloc(sizeof(LNode)); //分配一个新的节点内存空间,地址赋值给 L，即链表的头结点if(!L) return ERROR; //检查分配内存是否成功r=L;//初始化尾指针 r，让其指向头结点，因为初始时头结点就是最后一个节点。for(i=0; i<n; i++){ //使用循环遍历数组 E 中的元素，准备创建链表节点。if(!(p=(LinkList)malloc(sizeof(LNode))))//生成新结点return ERROR;p->data=E[i]; //将节点 p 的 data 域赋值为数组 E 中相应位置的元素值。r->next=p;//让当前尾节点 r 的 next 指针指向新节点 p，即将新节点插入到表尾。//******************************----------------3----------------r=p; //更新尾指针 r，将其指向新的表尾节点 p。 //******************************----------------4----------------}r->next=NULL; //将最后一个节点的 next 指针设为 NULL，表示链表的结束。return OK; //若所有节点创建成功，函数返回 OK，表示创建链表成功。}//在带有头结点的单链表 L 中的第 i 个位置之前插入元素 e。Status InsertLinkL(LinkList &L, int i, ElemType e) {LinkList s, p=L; int k=0; //初始化，p指向头结点,用于遍历，k为计数器while(p->next!=NULL && k<i-1) { //定位指针p指向第i-1个元素或p为空p=p->next;++k;}if(!p->next||k>i-1) return ERROR; //定位插入点失败if(!(s=(LinkList)malloc(sizeof(LNode)))) //申请元素e的结点空间return OVERFLOW; //内存无空闲单元，无法申请到空间s->data=e; //将新节点 s 的数据域赋值为要插入的元素 e s->next = p->next; //将新结点s插入到链表中//******************************----------------5----------------p->next = s; //将第 i-1 个元素指向新节点 s，完成节点的插入操作//******************************----------------6----------------return OK;}//按照位置删除节点Status Del_LinkL1(LinkList L,int i,ElemType &e) {int k=0;LinkList q,p=L;while(p->next!=NULL&&k<i-1) { //链表未到达末尾且未到达目标删除节点的前一个位置p=p->next;++k;}if(!p->next||k>i-1) return ERROR; //如果未找到要删除节点的前一个位置或者超出链表范围,则返回 ERRORq=p->next; //将 q 指向待删除节点，即第 i 个位置的节点 p->next = q->next; //将第 i-1 个节点指向待删除节点的下一个节点，从而跳过待删除节点//******************************----------------7----------------e=q->data; //将待删除节点中的数据保存在 e 变量中，以便外部代码可以访问被删除的节点值free(q); //释放待删除节点 q 所占用的内存空间，完成节点的删除操作return OK;}//按照值删除节点。大致内容同上，保姆累了 Status Del_LinkL2(LinkList &L,ElemType e) {LinkList p,q;p=L;q=L->next;while(q != NULL && q->data != e) {//******************************----------------8----------------p=q;q=q->next;}if(q==NULL)return ERROR;p->next=q->next;free(q);return OK;}//按照值删除节点，并删除所有匹配值的节点。用于删除链表 L 中数据域为 e 的节点。Status Del_LinkL3(LinkList &L,ElemType e) {LinkList p,q;int tag=FLASE; //定义一个标记变量 tag 并初始化为 FLASE，用于标记是否成功找到并删除节点。 p=L; //将指针 p 指向链表的头结点。q=L->next; //将指针 q 指向第一个有效节点，即头结点指向的第一个节点while(q!=NULL) {if(q->data==e){ //如果当前节点的数据域等于待删除的数据 e，执行下面的操作。p->next = q->next; //将前一个节点的指针指向当前节点的下一个节点，相当于跳过当前节点 q，从而将其删除。//******************************----------------9----------------free(q);tag=TRUE; //将标记 tag 设置为 TRUE，表示已找到并删除了节点。} elsep=q; //如果当前节点的数据域不等于待删除的数据 e，将 p 指向当前节点 q，准备处理下一个节点q=p->next; //将指针 q 指向下一个节点，继续遍历链表。}return tag;}void PrintLinkL(LinkList L) {LinkList p = L->next;while(p) {printf("%d→", p->data);p = p->next;}printf("∧\n");}void FreeLinkL(LinkList &L) {LinkList p, q;p = L;while(p != NULL) {q = p; // 将 q 指向当前节点 p//******************************----------------10----------------p = p->next; // 将 p 指向下一个节点free(q); // 释放当前节点 q 的内存}L = NULL; // 将链表头指针设置为 NULL，表示链表已被释放}int main() {ElemType E[]= {34,12,45,64,28,36,45,56}; //准备线性表int i,n=8;LinkList head;ElemType rc;printf("(1)表头插入法创建单链表......\n");if(!CreatLinkL1(head,n,E)) {printf(" 内存空间不够，创建失败! \n");return ERROR;} else {printf(" 创建完成。链表输出: ");PrintLinkL(head);}printf("(2)表尾插入法创建单链表......\n");FreeLinkL(head);if(!CreatLinkL2(head,n,E)) {printf(" 内存空间不够，创建失败! \n");return ERROR;} else {printf(" 创建完成。链表输出: ");PrintLinkL(head);}printf("(3)指定位置插入......\n");printf("输入插入位置和新元素值==>");scanf("%d%d",&i,&rc);if(!InsertLinkL(head,i,rc))printf(" 参数错误或内存空间不够，插入失败! \n");else {printf("插入成功！链表输出：");PrintLinkL(head);}printf("(4)删除指定位置节点......\n");printf("输入被删除节点位置==>");scanf("%d",&i);if(!Del_LinkL1(head,i,rc))printf("参数错误，删除失败!\n");else {printf("删除成功！被删除的节点键值是：%d\n 链表输出：",rc);PrintLinkL(head);}printf("(5)删除指定节点值......\n");printf("输入被删除键值==>");scanf("%d",&rc);if(!Del_LinkL2(head,rc))printf("输入的键值不存在！\n");else {printf("删除成功！键表输出：");PrintLinkL(head);}printf("(6)删除指定值所有节点.......\n");printf("输入所有被删节点的键值==>");scanf("%d",&rc);if(!Del_LinkL3(head,rc))printf("输入的键值不存在！\n");else {printf("删除成功！链表输出：");PrintLinkL(head);}printf("(7)清空链表......\n");FreeLinkL(head);PrintLinkL(head);if(!head)printf("链表已清空\n");elseprintf("清空链表失败！");}