關于頭結點,一般鏈表都會有頭結點,他會有幾個好處:
1. 開始起始點的位置放在頭結點的指針域中,這樣在頭結點的數據域可以存放一些其他數據,比如鏈表長度等。
2.?并且鏈表的第一個位置上的操作和其他位置的操作是一樣的,這樣空表和非空表的操作是一樣的。
// ? ?鏈表數據的定義,每個節點存放一個字符
~~~
typedef char datatype;
typedef struct node
{
datatype data;
struct node *next;
}linknode;
typedef linknode *linklist;
~~~
建立鏈表
~~~
//--------- 頭插法建立單鏈表
linklist CreatList(void)
{
datatype ch;
linklist head;
linknode *p;
head = NULL;
while((ch = getchar()) != '\n')
{
p = (linknode *)malloc(sizeof(linknode));
if(p == NULL)
{
printf("error: no space to get.\n");
return NULL;
}
p->data = ch;
p->next = head;
head = p;
}
return head;
}
//--------- 尾插法建立單鏈表,但是鏈表不帶頭結點
linklist CreatLinst2(void)
{
datatype ch;
linklist head;
linknode *p, *r;
head = NULL;
r = NULL;
while((ch = getchar()) != '\n')
{
p = (linknode *)malloc(sizeof(linknode));
p->data = ch;
if(head == NULL)
head = p;
else
r->next = p;
r = p;
}
if(r != NULL)
r->next = NULL;
return head;
}
~~~
//---------?尾插法建立單鏈表,帶頭結點,頭結點暫時沒有存放什么東西,可以存放鏈表的長度信息等。
~~~
linklist CreatList1(void)
{
datatype ch;
linklist head;
linknode *p, *r;
head = (linknode *)malloc(sizeof(linknode));
if(head == NULL)
{
printf("error: no space to get.\n");
return NULL;
}
r = head;
while((ch = getchar()) != '\n')
{
p = (linknode *)malloc(sizeof(linknode));
p->data = ch;
r->next = p;
r = p;
}
r->next = NULL;
return head;
}
~~~
刪除鏈表
~~~
//--------------------------- 沒有頭節點的話,刪除的i值不能小于1,為1時其實是刪除了首節點的后面的那一個節點。 (首節點不是頭結點哈)
//刪除節點的時候,這個函數不能刪除的第一個節點,有頭節點的話就不能刪除頭結點,沒有的話就不能刪除首節點。
void DeleteNode(linklist head, int i)
{
int j = 0;
linknode *p = head, *t;
while(p && j < i-1)
{
p = p->next;
j++;
}
if(!p || j>i-1)
exit(1);
t = p->next;
p->next = t->next;
free(t);
}
~~~
插入鏈表
//-------------------第一個節點的序號是0,如果有頭節點的話,頭結點的序號就是0
~~~
void InsetNode(linklist head, datatype x, int i)
{
int j = 0;
linknode *p, *t;
p = head;
while(p && j < i-1)
{
p = p->next;
j++;
}
if(!p || j >i-1)
exit(1);
t = (linknode *)malloc(sizeof(linknode));
t->data = x;
t->next = p->next;
p->next = t;
}
~~~
查找鏈表
~~~
// -------------------------------按序號查找--------------------------------
linklist GetNode(linklist head, int i)
{
int j = 0;
linknode *p = head;
while(p->next && j<i)
{
p = p->next;
j++;
}
if(i == j)
return p;
else
return NULL;
}
~~~
// -------------------------------按值查找---------------------------
~~~
linklist locatenode(linklist head, datatype key)
{
linklist p = head;
while(p && p->data!=key)
{
p = p->next;
}
return p;
}
~~~
顯示鏈表
~~~
//------------- 無頭結點的顯示鏈表
void ShowList(linklist head)
{
linklist p = head;
while(p != NULL)
{
printf("%c", p->data);
head = head->next;
p = head;
}
printf("\n");
}
~~~
釋放鏈表
~~~
void FreeList(linklist head)
{
linklist p = head;
while(p != NULL)
{
head = head->next;
free(p);
p = head;
}
printf("\nfree list is ok.\n");
}
~~~