#include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct Node { int data;//數據域 struct Node *pNext;//指針域 }NODE,*PNODE; PNODE CreateList();//創建鏈表 void TraverseList(PNODE);//遍歷鏈表 bool IsEmpty(PNODE);//判斷鏈表是否為空 int Length(PNODE);//求鏈表長度 bool InsertNode(PNODE,int,int);//插入結點 bool DeleteNode(PNODE,int,int *);//刪除結點 bool QueryNode(PNODE,int);//查找結點 bool ModifyNode(PNODE,int,int);//修改結點 void SortList(PNODE);//排序 int main() { PNODE pHead=NULL; pHead=CreateList();//將創建鏈表的頭指針的地址賦給pHead if(0==Length(pHead)) { printf("鏈表無有效節點,退出程序!\n"); exit(-1); } TraverseList(pHead); if(InsertNode(pHead,2,100)) { printf("插入後"); TraverseList(pHead); } else { printf("插入操作失敗!\n"); } SortList(pHead); printf("排序後"); TraverseList(pHead); return 0; } PNODE CreateList() { int len;//用來保存需要創建鏈表的結點個數 int i; int val;//用來臨時存放新節點的值 PNODE pHead=(PNODE)malloc(sizeof(NODE));//動態分配一塊內存,該內存保存頭結點的地址,並將其賦給pHead PNODE pTail=pHead; PNODE pNew; pTail->pNext=NULL;//將尾結點的指針域賦為NULL if(NULL==pHead) { printf("分配失敗,程序終止運行!\n"); exit(-1); } printf("請輸入你要創建鏈表的結點個數:len="); scanf("%d",&len); for(i=0;i<len;i++) { printf("請輸入第%d個結點的值:",i+1); scanf("%d",&val); pNew=(PNODE)malloc(sizeof(NODE));//創建新臨時結點 if(NULL==pNew) { printf("分配失敗,程序終止運行!\n"); exit(-1); } pNew->data=val; pTail->pNext=pNew;//將新結點掛到原尾結點的後面 pNew->pNext=NULL;//將新結點的指針域賦為NULL pTail=pNew;//將新結點置為尾結點 } return pHead; } void TraverseList(PNODE pHead) { PNODE p=pHead->pNext;//將頭結點的指針域指向首結點(鏈表的第一個有效結點),並賦給指針變量p,此時p指向首節點的地址 printf("遍歷整個鏈表:"); while(NULL!=p)//當p指向首節點的地址不為NULL(即鏈表不為空),循環輸入個結點的值 { //當p指向尾結點的地址時,可輸出尾結點的值 //但此時尾結點指針域為NULL,將跳出while循環 printf("%d ",p->data); p=p->pNext;//將p指向下一個結點的地址賦給p指針 } printf("\n"); } bool IsEmpty(PNODE pHead) { if(NULL==pHead->pNext) return true; else return false; } int Length(PNODE pHead) { PNODE p=pHead->pNext;//此時p指向鏈表的首結點(第一個有效結點)的地址 int len=0; while(NULL!=p) { ++len; p=p->pNext; } return len; } bool InsertNode(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead,q; PNODE pNew; while(NULL!=p&&i<pos-1)//目的是為了使p指向要插入位置的前一個結點 { p=p->pNext; ++i;//如鏈表只有兩個有效結點,要插入的位置結點pos=3,i=2時,2<3-1不成立,循環結束, } if(i>pos-1||NULL==p)//p為NULL說明要插入位置結點的前一個結點不存在,i>pos-1是為了防止用戶輸入pos為像0、-1等非法數據 return false; pNew=(PNODE)malloc(sizeof(NODE));//為新節點分配內存 if(NULL==pNew) { printf("動態內存分配失敗,程序終止!\n"); exit(-1); } pNew->data=val; q=p->pNext; p->pNext=pNew; pNew->pNext=q; return true; } bool DeleteNode(PNODE pHead,int pos,int *pVal) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; *pVal=q->data; p->pNext=p->pNext->pNext; free(q); q=NULL; return true; } void SortList(PNODE pHead) { int i,j,t; int len=Length(pHead);//用len來保存鏈表的長度 PNODE p,q; for(i=0,p=pHead->pNext;i<len-1;p=p->pNext,i++)//比較趟數 { for(j=i+1,q=p->pNext;j<len;q=q->pNext,j++)//比較對數 { if(p->data>q->data) { t=p->data; p->data=q->data; q->data=t; } } } } bool QueryNode(PNODE pHead,int pos) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; printf("第%d號位置上結點的值為:%d\n",pos,q->data); return true; } bool ModifyNode(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; q->data=val; printf("修改第%d號位置上結點的值為:%d\n",pos,q->data); return true; } #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct Node { int data;//數據域 struct Node *pNext;//指針域 }NODE,*PNODE; PNODE CreateList();//創建鏈表 void TraverseList(PNODE);//遍歷鏈表 bool IsEmpty(PNODE);//判斷鏈表是否為空 int Length(PNODE);//求鏈表長度 bool InsertNode(PNODE,int,int);//插入結點 bool DeleteNode(PNODE,int,int *);//刪除結點 bool QueryNode(PNODE,int);//查找結點 bool ModifyNode(PNODE,int,int);//修改結點 void SortList(PNODE);//排序 int main() { PNODE pHead=NULL; pHead=CreateList();//將創建鏈表的頭指針的地址賦給pHead if(0==Length(pHead)) { printf("鏈表無有效節點,退出程序!\n"); exit(-1); } TraverseList(pHead); if(InsertNode(pHead,2,100)) { printf("插入後"); TraverseList(pHead); } else { printf("插入操作失敗!\n"); } SortList(pHead); printf("排序後"); TraverseList(pHead); return 0; } PNODE CreateList() { int len;//用來保存需要創建鏈表的結點個數 int i; int val;//用來臨時存放新節點的值 PNODE pHead=(PNODE)malloc(sizeof(NODE));//動態分配一塊內存,該內存保存頭結點的地址,並將其賦給pHead PNODE pTail=pHead; PNODE pNew; pTail->pNext=NULL;//將尾結點的指針域賦為NULL if(NULL==pHead) { printf("分配失敗,程序終止運行!\n"); exit(-1); } printf("請輸入你要創建鏈表的結點個數:len="); scanf("%d",&len); for(i=0;i<len;i++) { printf("請輸入第%d個結點的值:",i+1); scanf("%d",&val); pNew=(PNODE)malloc(sizeof(NODE));//創建新臨時結點 if(NULL==pNew) { printf("分配失敗,程序終止運行!\n"); exit(-1); } pNew->data=val; pTail->pNext=pNew;//將新結點掛到原尾結點的後面 pNew->pNext=NULL;//將新結點的指針域賦為NULL pTail=pNew;//將新結點置為尾結點 } return pHead; } void TraverseList(PNODE pHead) { PNODE p=pHead->pNext;//將頭結點的指針域指向首結點(鏈表的第一個有效結點),並賦給指針變量p,此時p指向首節點的地址 printf("遍歷整個鏈表:"); while(NULL!=p)//當p指向首節點的地址不為NULL(即鏈表不為空),循環輸入個結點的值 { //當p指向尾結點的地址時,可輸出尾結點的值 //但此時尾結點指針域為NULL,將跳出while循環 printf("%d ",p->data); p=p->pNext;//將p指向下一個結點的地址賦給p指針 } printf("\n"); } bool IsEmpty(PNODE pHead) { if(NULL==pHead->pNext) return true; else return false; } int Length(PNODE pHead) { PNODE p=pHead->pNext;//此時p指向鏈表的首結點(第一個有效結點)的地址 int len=0; while(NULL!=p) { ++len; p=p->pNext; } return len; } bool InsertNode(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead,q; PNODE pNew; while(NULL!=p&&i<pos-1)//目的是為了使p指向要插入位置的前一個結點 { p=p->pNext; ++i;//如鏈表只有兩個有效結點,要插入的位置結點pos=3,i=2時,2<3-1不成立,循環結束, } if(i>pos-1||NULL==p)//p為NULL說明要插入位置結點的前一個結點不存在,i>pos-1是為了防止用戶輸入pos為像0、-1等非法數據 return false; pNew=(PNODE)malloc(sizeof(NODE));//為新節點分配內存 if(NULL==pNew) { printf("動態內存分配失敗,程序終止!\n"); exit(-1); } pNew->data=val; q=p->pNext; p->pNext=pNew; pNew->pNext=q; return true; } bool DeleteNode(PNODE pHead,int pos,int *pVal) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; *pVal=q->data; p->pNext=p->pNext->pNext; free(q); q=NULL; return true; } void SortList(PNODE pHead) { int i,j,t; int len=Length(pHead);//用len來保存鏈表的長度 PNODE p,q; for(i=0,p=pHead->pNext;i<len-1;p=p->pNext,i++)//比較趟數 { for(j=i+1,q=p->pNext;j<len;q=q->pNext,j++)//比較對數 { if(p->data>q->data) { t=p->data; p->data=q->data; q->data=t; } } } } bool QueryNode(PNODE pHead,int pos) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; printf("第%d號位置上結點的值為:%d\n",pos,q->data); return true; } bool ModifyNode(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead,q; while(NULL!=p->pNext&&i<pos-1) { p=p->pNext; ++i; } if(i>pos-1||NULL==p) return false; q=p->pNext; q->data=val; printf("修改第%d號位置上結點的值為:%d\n",pos,q->data); return true; }
注意: 1.在vc++中,c編譯器不支持bool函數,但c++編譯器支持,所以這裡我用的是c++編譯器。 2.c編譯過程中常見錯誤:illegal use of this type as an expression 是由於c語言不允許臨時定義變量,所有定義的變量都必須放在函數開頭,這也是c和c++的重要區別 數據結構的再理解 狹義上的理解:數據結構是專門研究數據存儲(包括個體的存儲和個體關系的存儲)問題。 廣義上的理解:數據結構既包含數據的存儲也包含數據的操作。算法是對存儲數據的操作。 算法: 狹義上的理解:算法和數據的存儲方式密切相關 廣義上的理解:算法和數據的存儲方式無關(這就是泛型的思想) 泛型:利用某種技術達到的效果就是不同的存儲方式,執行的操作是一樣的。泛型主要通過模板,運算符的重載,指針來實現,在c++中經常用到。 補充 線性結構: 連續存儲【數組】 優點:存取速度快 缺點:插入刪除元素很慢,空間通常是有限制的,事先必須知道數組的長度,而且需要大塊連續內存塊 離散存儲【鏈表】 優點:插入刪除元素很快,空間沒有限制的; 缺點: 存取速度很慢