線性表--鏈式實現方式

 鏈式方式的線性表。

                    在實現之前首先需要對其線性表的鏈式方式的特點做一個了解：

            通俗的講鏈式線性表就是元素之間邏輯相鄰但是物理位置不一定相鄰，那麼既然物理位置不相鄰

            又是如何來體現其邏輯位置的呢？其邏輯關系是上一個元素來維護的。鏈式線性表的每個元素是

            保存在結點中的，結點就是一塊內存區域。它包含兩個區域數據域、指針域。數據域保存元素值

            指針域保存下一個結點指向性。

                 具體如何呢？看看結點數據結構吧：

[cpp] v
typedef  struct LNode 
{ 
    ElemType data;//節點數據信息域  
    struct LNode * next;//指向下一個節點的指針  
}LNode ,*LinkList; 

typedef  struct LNode
{
 ElemType data;//節點數據信息域
 struct LNode * next;//指向下一個節點的指針
}LNode ,*LinkList;
               之後我們來看看其具體的實現和操作，在對鏈式線性表做一個總結

[cpp]
/**
  Author Kiritor
  線性表的鏈式實現*/ 
#include "stdafx.h"  
#include<stdio.h>  
#include<stdlib.h>  
#include<conio.h>  
#include<malloc.h>  
#define OK 1  
#define OVERFLOW -1  
#define ERROR -1  
#define TRUE 1  
#define FALSE 0  
#define ElemType int  
//線性表的單鏈表存儲結構  
typedef  struct LNode 
{ 
    ElemType data;//節點數據信息域  
    struct LNode * next;//指向下一個節點的指針  
}LNode ,*LinkList; 
 
//初始化單鏈表  
int init_List(LinkList &l) 
{ 
    printf("初始化線性表\n"); 
    //產生一個頭結點，並且使L指向頭結點  
    l = (LinkList)malloc(sizeof(LNode)); 
    if(!l) 
        exit(OVERFLOW);//分配空間失敗  
    l->next=NULL;//頭結點的指針域為空表示無元素  
    l->data= 0;//頭結點數據域用於表示鏈表的長度  
    return OK; 
} 
 
//銷毀鏈式單向線性表  
void destory_List(LinkList &l) 
{ 
    printf("銷毀線性表"); 
    LinkList q ; 
    /*循環的釋放每一個結點的內存空間*/ 
    while(l) 
    { 
        q=l->next; 
        free(l); 
        l=q; 
    } 
} 
 
//將線性表重新置為空表，並非銷毀  
int clear_List(LinkList &l) 
{ 
    printf("清空線性表，並非銷毀\n"); 
    LinkList p,q; 
    p=l->next;//p指向第一個結點  
    while(p) 
    { 
        q= p->next; 
        free(p); 
        p=q; 
    } 
    //之後將頭指針域的指向性設置為空  
    l->next = NULL; 
    l->data=0; 
    return OK; 
} 
//線性表插入(帶頭結點的)  
//在第i個位置之前插入e，i值從1開始  
int insert_List(LinkList &l,int i,ElemType e) 
{ 
    printf("在第%d個位置插入%d\n",i,e); 
    //首先尋找第i個結點  
    LinkList q = l,s; 
    int j=0;//用於循環的計數器  
    while(q&&j<i-1) 
    { 
        q = q->next; 
        j++; 
    } 
    if(!q||j>i-1) 
    { 
        return ERROR; 
    } 
    s=(LinkList)malloc(sizeof(LNode));//生成一個新的結點  
    s->data=e; 
    s->next=q->next; 
    q->next =s; 
    l->data++;//線性表的長度加1  
    return OK; 
} 
 
/*取得線性表的i位置的元素，存在返回ok，並將之存在e中
  反之返回ERROR，需要注意的是l是帶頭結點的單鏈表
*/ 
int getElem(LinkList l,int i,ElemType &e) 
{ 
    LNode * p = l->next ; 
    int count = 1; 
    //初始化，使p指向第一個結點，count為計數器  
    while(p&&count < i) 
    { 
        p = p ->next ; 
        count++; 
    } 
    //p指針移動到要取得的元素位置的結點處  
    if(!p||count >i) 
        return ERROR; 
    e=p->data; 
    return e; 
} 
/*判斷線性表是否為空*/ 
int isEmpty(LinkList &l) 
{ 
     if(l->data==0) 
         return FALSE; 
     else 
         return TRUE; 
      
} 
/*刪除線性表中的某個位置元素
i是從1開始的**/ 
int delete_LinkList(LinkList &l,int i) 
{ 
    printf("刪除線性表%d位置的元素\n",i); 
    int j=0; 
    LinkList p = l; 
    //首先找到要刪除的元素的位置  
    while (p->next&&i>=1&&j<i-1) 
    { 
        p=p->next; 
        j++; 
    } 
    if(!p->next||j>i-1) 
        return ERROR;//刪除的位置不合理  
    LinkList q = p->next; 
    p->next = q->next; 
    free(q); 
    l->data--; 
    return OK; 
} 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    LinkList l; 
    int e; 
    init_List(l); 
    insert_List(l,1,3); 
    insert_List(l,1,4); 
    insert_List(l,1,5); 
    insert_List(l,1,6); 
    printf("第一個位置的元素為%d\n",getElem(l,1,e)); 
    printf("線性表的元素個數;%d\n",l->data); 
    clear_List(l); 
    destory_List(l); 
    _getch(); 
    return 0; 
} 

/**
  Author Kiritor
  線性表的鏈式實現*/
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#define OK 1
#define OVERFLOW -1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define ElemType int
//線性表的單鏈表存儲結構
typedef  struct LNode
{
 ElemType data;//節點數據信息域
 struct LNode * next;//指向下一個節點的指針
}LNode ,*LinkList;

//初始化單鏈表
int init_List(LinkList &l)
{
 printf("初始化線性表\n");
 //產生一個頭結點，並且使L指向頭結點
 l = (LinkList)malloc(sizeof(LNode));
 if(!l)
  exit(OVERFLOW);//分配空間失敗
 l->next=NULL;//頭結點的指針域為空表示無元素
 l->data= 0;//頭結點數據域用於表示鏈表的長度
 return OK;
}

//銷毀鏈式單向線性表
void destory_List(LinkList &l)
{
 printf("銷毀線性表");
 LinkList q ;
 /*循環的釋放每一個結點的內存空間*/
 while(l)
 {
  q=l->next;
  free(l);
  l=q;
 }
}

//將線性表重新置為空表，並非銷毀
int clear_List(LinkList &l)
{
 printf("清空線性表，並非銷毀\n");
 LinkList p,q;
 p=l->next;//p指向第一個結點
 while(p)
 {
  q= p->next;
  free(p);
  p=q;
 }
 //之後將頭指針域的指向性設置為空
 l->next = NULL;
 l->data=0;
 return OK;
}
//線性表插入(帶頭結點的)
//在第i個位置之前插入e，i值從1開始
int insert_List(LinkList &l,int i,ElemType e)
{
 printf("在第%d個位置插入%d\n",i,e);
 //首先尋找第i個結點
 LinkList q = l,s;
 int j=0;//用於循環的計數器
 while(q&&j<i-1)
 {
  q = q->next;
  j++;
 }
 if(!q||j>i-1)
 {
  return ERROR;
 }
 s=(LinkList)malloc(sizeof(LNode));//生成一個新的結點
 s->data=e;
 s->next=q->next;
 q->next =s;
 l->data++;//線性表的長度加1
 return OK;
}

/*取得線性表的i位置的元素，存在返回ok，並將之存在e中
  反之返回ERROR，需要注意的是l是帶頭結點的單鏈表
*/
int getElem(LinkList l,int i,ElemType &e)
{
 LNode * p = l->next ;
 int count = 1;
 //初始化，使p指向第一個結點，count為計數器
 while(p&&count < i)
 {
  p = p ->next ;
  count++;
 }
 //p指針移動到要取得的元素位置的結點處
 if(!p||count >i)
  return ERROR;
 e=p->data;
 return e;
}
/*判斷線性表是否為空*/
int isEmpty(LinkList &l)
{
  if(l->data==0)
   return FALSE;
  else
   return TRUE;
 
}
/*刪除線性表中的某個位置元素
i是從1開始的**/
int delete_LinkList(LinkList &l,int i)
{
 printf("刪除線性表%d位置的元素\n",i);
 int j=0;
 LinkList p = l;
 //首先找到要刪除的元素的位置
 while (p->next&&i>=1&&j<i-1)
 {
  p=p->next;
  j++;
 }
 if(!p->next||j>i-1)
  return ERROR;//刪除的位置不合理
 LinkList q = p->next;
 p->next = q->next;
 free(q);
 l->data--;
 return OK;
}
int _tmain(int argc, _TCHAR* argv[])
{
 LinkList l;
 int e;
 init_List(l);
 insert_List(l,1,3);
 insert_List(l,1,4);
 insert_List(l,1,5);
 insert_List(l,1,6);
 printf("第一個位置的元素為%d\n",getElem(l,1,e));
 printf("線性表的元素個數;%d\n",l->data);
 clear_List(l);
 destory_List(l);
 _getch();
 return 0;
}

              看看程序的執行結果：

         上述執行最重要的還是插入和刪除的操作！

            插入操作過程：

                  刪除操作過程：

                  通過代碼的閱讀就可以看出，鏈式方式的線性表和順序方式的線性表的主要區別

              在於物理地址上的不連續，而且順序方式對於插入刪除元素開銷比鏈式方式大，但是

              順序方式取得元素的時候更加方便。因此選取那種線性表的時候需要根據實際情況來定！