数据结构实验2.zip

4.14KB

1 需要积分: 1

立即下载

资源介绍:

数据结构实验2.zip

#define OVERFLOW -1 #define OK 1 #define ERROR 0 #define TRUE 1 #define FLASE 0 #include #include #include //用于内存分配 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; //指向链表节点的指针 p L=(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; idata=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 && knext; ++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&&knext; ++k; } if(!p->next||k>i-1) return ERROR; //如果未找到要删除节点的前一个位置或者超出链表范围,则返回 ERROR q=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，表示已找到并删除了节点。 } else p=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"); else printf("清空链表失败！"); }

资源文件列表:

数据结构实验2.zip 大约有2个文件

数据结构实验2/2.1.cpp 7.65KB
数据结构实验2/2.2.cpp 2.84KB