数据结构学习总结ing
//初始化、判空、按位序插入、指定结点后插操作、指定结点前插操作、按位序删除、指定结点的删除、 //按位查找、按值查找、求表长、尾插法、头插法、输出 #include <stdio.h> #include <stdlib.h>//malloc,free函数库 typedef int ElemType;//int另命名 typedef struct LNode{//定义单链表结点类型 ElemType data;//每个结点存放一个数据元素 struct LNode *next;//next指针，指向下一个节点 }LNode,*LinkList; //此处应注意：强调一个单链表使用LinkList、强调一个结点使用LNode * //注意此时申请结点代码：LNode *p=(LNode *)malloc(sizeof(LNode)); //注意此时申请头结点代码：L=(LNode *)malloc(sizeof(LNode)); 此时返回给L的是一个指针，并且赋给了头指针（L已声明） bool InitList(LinkList &L){//初始化一个单链表（带头结点） L=(LNode *)malloc(sizeof(LNode));//分配一个头结点 if(L==NULL)//内存不足，分配失败 return false; L->next=NULL;//头结点之后暂时还没有结点 return true; } bool Empty(LinkList L){//判断单链表是否为空（带头结点） if(L->next==NULL) return true; else return false; } bool ListInsert(LinkList &L,int i,ElemType e){//按位序插入,在第i个位置插入e if(i<1)//i值不合法 return false; LNode *p;//声明指针p，用于指向当前扫描到的结点 int j=0;//当前p指向的是第几个结点 //注意：此时j=0 p=L;//p指向头结点，头结点是第0个结点（不存数据） while(p!=NULL && j<i-1){//循环找到第i-1个结点 p=p->next; j++; } if(p==NULL)//i值不合法 return false; LNode *s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true; } bool InsertNextNode(LNode *p,ElemType e){//指定结点后插操作，在p结点之后插入e if(p==NULL)//判空 return false; LNode *s=(LNode *)malloc(sizeof(LNode));//申请s结点 if(s==NULL)//内存分配失败 return false; s->data=e;//用结点s保存数据元素e s->next=p->next;//s的next指针指向p的下一个结点 p->next=s;//p的next指针指向s结点，也就是将结点s连到p之后 return true; } bool InsertPriorNode(LNode *p,ElemType e){//指定结点前插操作，在p结点之前插入e if(p==NULL)//判空 return false; LNode *s=(LNode *)malloc(sizeof(LNode));//申请s结点 if(s==NULL)//内存分配失败 return false; s->next=p->next;//s的next指针指向p的下一个结点 p->next=s;p的next指针指向s结点，也就是将结点s连到p之后 s->data=p->data;//将p的数据元素复制到s中 p->data=e;//将e覆盖到p中 return true; } bool ListDelete(LinkList &L,int i,ElemType &e){//按位序删除（带头结点） if(i<1)//i值不合法 return false; LNode *p;//声明结点p，p指向当前扫描到的结点 int j=0;//声明j变量，j表示当前p指向的是第几个结点 p=L;//L指向头结点，此时头结点是第0个结点（不存数据），此处可和上面代码合写为LNode *p=L; while(p!=NULL && j<i-1){//循环找到第i-1个结点 p=p->next; j++; } if(p==NULL)//i值不合法 return false; if(p->next==NULL)//第i-1个结点之后已无其他结点 return false; LNode *q=p->next;//声明结点q，q指向p的下一个结点，此时q指向被删除结点 e=q->data;//用e返回元素的值 p->next=q->next;// p的next指针指向q的下一个结点,也就是将*q结点从链中断开 free(q);//释放q结点的存储空间 return true; } bool DeleteNode(LNode *p){//指定结点的删除 if(p==NULL)//判空 return false; LNode *q=p->next;//声明结点q，q指向被删除结点 p->data=p->data;//用e返回元素的值 p->next=q->next;// p的next指针指向q的下一个结点,也就是将*q结点从链中断开 free(q);//释放q结点的存储空间 return true; } LNode *GetElem(LinkList L,int i){//按位查找，返回第i个元素（带头结点） if(i<0) return NULL; LNode *p;//声明结点p，p指向当前扫描到的结点 int j=0;//声明j变量，j表示当前p指向的是第几个结点 p=L;//L指向头结点，头结点是第0个结点（不存数据），此处可和上面代码合写为LNode *p=L; while(p!=NULL && j<i){//循环找到第i个结点 p=p->next; j++; } return p; } LNode *LocateElem(LinkList L,ElemType e){//按值查找（带头结点） LNode *p=L->next;//从第i个结点开始查找数据域为e的结点 //注意：LNode *p=L->next;语句说的是声明p指针指向头结点L的下一个结点 //注意：LNode *p=L;语句说的是声明p指针指向头结点L while(p!=NULL&&p->data!=e) p=p->next;//找到后返回该结点指针，否则返回NULL return p; } int Length(LinkList L){//求表长（带头结点） int len=0; LNode *p=L;//声明p指针指向头结点L while(p->next!=NULL){ p=p->next; len++; } return len; } LinkList List_TailInsert(LinkList &L){//尾插法建立单链表（带头结点） int x; L=(LinkList)malloc(sizeof(LNode));//建立头结点,注意此处返回的是LinkList，初始化空表 LNode *s; LNode *r=L;//r为表尾指针 scanf("%d",&x);//输入结点的值 while(x!=999){ s=(LNode *)malloc(sizeof(LNode));//创建新结点（此时s结点已在循环体外声明） s->data=x; r->next=s; r=s;//r指向新的表尾结点 scanf("%d",&x); } r->next=NULL;//尾结点指针置空 return L; } LinkList List_HeadInsert(LinkList &L){//头插法建立单链表（带头结点） LNode *s; int x; L=(LinkList)malloc(sizeof(LNode));//创建头结点 L->next=NULL;//初始化为空链表，养成好习惯，只要是初始化单链表，都应该先把头指针指向NULL scanf("%d",&x); while(x!=9999){ s=(LNode *)malloc(sizeof(LNode));//创建新结点（此时s结点已在循环体外声明） s->data=x; s->next=L->next; L->next=s;//将新结点插入表中，L为头指针 scanf("%d",&x); } return L; } void DispList(LinkList L){//输出 int i=1; LNode *p=L->next;//定义一个结点指针p指向头结点的下一个结点 while(p!=NULL){ //如果p不为空则循环 printf("第%d个元素为%d\n",i,p->data); p=p->next;//移动指针p遍历链表 i++; } } int main(){ LinkList L; List_HeadInsert(L); DispList(L); //... return 0; }