對鏈表的相關操作及數據結構的再理解

結點的操作           由於鏈表是n個離散結點彼此通過指針相連，所以對鏈表的相關操作主要通過頭指針(存放了頭結點的地址)對結點進行操作來實現。          1.如何將q所指向的結點插入到p所指向結點的後面？                   有兩個方法                       第一種： 采用臨時變量                           r=p->pNext;//用r保存p所指向結點的下一個結點地址                           p->pNext=q;//此時p的指針域指向q所指的結點的地址                          q->pNext=r;                        第二種：不采用臨時變量                             q-pNext=p->pNext;//讓p和q所指向結點的指針域指向後面的同一個結點                             p-pNext=q;//再讓p的指針域指向q結點              2.如何刪除一個節點(思路：用一個臨時變量r來保存要刪除的結點，再刪除p後面的那個結點)                             r=p->pNext;                               p->pNext=p->pNext->pNext;                                        free(r);                             r=NULL;                                            3.如何判斷鏈表是否為空(思路：空鏈表只有一個頭結點，所以只需讓頭結點的指針域為NULL即可)         對鏈表的相關操作     實例說明：   

#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++中經常用到。       補充          線性結構：                   連續存儲【數組】                            優點：存取速度快                            缺點：插入刪除元素很慢，空間通常是有限制的，事先必須知道數組的長度，而且需要大塊連續內存塊                     離散存儲【鏈表】                            優點：插入刪除元素很快，空間沒有限制的；                            缺點： 存取速度很慢