数据结构第二章线性表c++代码

#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指向下一个结点 }LNode,*LinkList;//LinkList等价于struct LNode *，LNode等价于 struct LNode //头插法创建链表 LinkList CreateList1(LinkList &L){ LNode *s;int x; L=(LinkList)malloc(sizeof(LNode));//带头结点链表 L->next=NULL;//L->data中不放数据 scanf("%d",&x);//输入数据 //3 4 5 6 7 9999 while(x!=9999){ s=(LNode*)malloc(sizeof(LNode));//申请一个新空间，强制类型转换 s->data=x;//赋值给新结点 s->next=L->next;//新结点的下一个结点指向原链表的下一个结点 L->next=s;//再把原链表下一个指向新节点s scanf("%d",&x); } return L; } //尾插法创建链表 LinkList CreateList2(LinkList &L){ int x; L=(LinkList)malloc(sizeof(LNode));//带头结点链表 LNode *s,*r=L; //等价于LinkList s,r=L;//r尾指针 scanf("%d",&x);//输入数据 //3 4 5 6 7 9999 while(x!=9999){ s=(LNode*)malloc(sizeof(LNode));//申请一个新空间，强制类型转换 s->data=x;//赋值给新结点 r->next=s;//新结点指向原链表尾指针的下一个结点 r=s;//再把新节点s赋值给尾指针r scanf("%d",&x); } r->next=NULL;//尾指针的next赋值给null 不设置的话会发生错误默认不为null，为cdcdcd，计算机默认不可访问 return L; } //按位置查找 LNode *GetElem(LinkList L,int i){ int j=1;//计数，初始化为一 LNode *p=L->next;//把第一个结点指针赋给p if(i==0){ return L;//若i等于0，则返回头结点 } if(i<1){ return NULL;//若i无效，则返回NULL } while(p&&j<i){//从第一个结点开始找，查找第i个结点 p=p->next; j++; } return p;//返回第i个结点指针，若i大于表长，则返回NULL } //按值查找 LNode *LocateElem(LinkList L,ElemType e){ LNode *p=L->next;//把第一个结点指针赋给p while(p!=NULL&&p->data!=e){//从第一个结点开始找，查找结点值为e p=p->next; } return p;//返回结点指针，否则返回NULL } //插入结点 bool ListFrontInsert(LinkList L,int i,ElemType e){ LinkList p=GetElem(L,i-1);//查找插入位置的前驱 if(p==NULL){ return false; } LinkList s=(LinkList)malloc(sizeof(LNode));//申请一个新空间，强制类型转换 s->data=e; s->next=p->next; p->next=s; return true; } //插入结点 自己写的，跟老师写的差一丢丢 void ListFrontInsert2(LinkList L,int i,ElemType e){ LNode *s,*p; p=GetElem(L,i-1);//查找插入位置的前驱 s=(LNode*)malloc(sizeof(LNode));//申请一个新空间，强制类型转换 s->data=e; s->next=p->next; p->next=s; } //删除结点 bool ListDelete(LinkList L,int i){ LinkList p=GetElem(L,i-1);//查找删除位置的前驱结点 if(p==NULL){ return false; } // LinkList q=(LinkList)malloc(sizeof(LNode));//申请一个新空间，强制类型转换 LinkList q=p->next; if(q==NULL){//删除的元素不存在 return false; } p->next=q->next;//断链 free(q); q=NULL;//避免野指针 return true; } //删除结点 自己写的 void ListDelete2(LinkList L,int i){ LNode *p,*q; p=GetElem(L,i-1);//查找删除位置的前驱结点 q=p->next; p->next=q->next; free(q); q=NULL;//避免野指针 } //打印链表 void PrintList(LinkList L){ L=L->next; while(L!=NULL){ printf("%3d",L->data); L=L->next; } printf("\n"); } int main(){ LinkList L;//链表头，是结构体指针类型 LinkList search;//用来存储拿到的某一个结点 //建链表 CreateList1(L);//输入数据为3 4 5 6 7 9999为结束循环标志 PrintList(L);//打印链表 // CreateList2(L);//尾插法创建链表 // PrintList(L);//打印链表 //查找 search=GetElem(L,2); if(search!=NULL){ printf("按序号查找成功\n"); printf("%d\n",search->data); } search=LocateElem(L,6);//按值查找 if(search!=NULL){ printf("按值查找成功\n"); printf("%d\n",search->data); } //插入 ListFrontInsert(L,2,98);//新结点插入 // ListFrontInsert2(L,2,98);//新结点插入 PrintList(L); //删除 ListDelete(L,4);//删除第四个结点 // ListDelete2(L,4);//删除第四个结点 PrintList(L); }