c语言中头结点不为零怎么写,C语言不带表头结点的单链表操作
什么是鏈表
簡單理解為鏈表的功能與數組功能相似用來存儲數據，鏈表作為一種基本的數據結構在程序開發過程當中經常會使用到。對C語言來說鏈表的實現主要依靠結構體(可以存儲多種數據類型)和指針，所以本文相關內容和程序需要有C語言當中指針和結構體的基礎。
為什么使用鏈表
1、解決數組無法存儲多種數據類型的問題。
2、解決數組中，元素個數無法改變的限制。
3、數組移動元素的過程中，要對元素進行大范圍的移動，很耗時間，效率也不高。
鏈表的組成
1、鏈表由節點組成。
2、節點由值域與指針域組成。
3、還需要一個頭指針指向鏈表(例如一個指針指向一個數組，那么數組名也可以代表此數組的首地址)
4、鏈表的基本表示
struct node //表示圖片中的體
{
int num;
char a;
struct node *next; //指向下一個相同數據類型的結構體，next存放下一個結點的地址
}
> head頭指針指向頭結點，其中頭結點的next指針指向下一個節點的頭，一次類推直到最后一個節點的尾指針指向NULL(空指針)時離鏈表結束。
(這里的體是結構體類型，next是指向下一個結點的指針，結點的組成：數據域(體是數據域的一種體現)+(指針域) )
鏈表的特點
1、鏈表結點可以連續，可以不連續存儲。
2、結點的邏輯順序與物理順序可以不一致。
3、表可擴充。
邏輯順序與物理順序的理解
可以使用的存儲空間
解釋：各個結點的物理存儲位置可能不是連續的，a0后面是a2而不是a1，但是每個結點的尾地址都是按照邏輯順序指向下一個結點的。(意思就是說我有10個抽屜，每個抽屜編號1~10，但是這10個抽屜不是按順序擺放，將撲克牌A到10一次按抽屜順序放入10個抽屜里，每次取按順序取出，例如第一個抽屜在第1層，里面是A，接下來要去2但是存放2的抽屜在第5層因此要去第5層取2)
怎么插入一個節點
在頭結點的后面插入一個節點
插入一個中間節點
在頭節點前面插入節點(頭插)
尾插
1、
將一個新的結點插入到最后一個節點的后面，先將前一個尾結點的地址指向新結點的地址P，然后再將新結點的指針域改成NULL。
2、
頭插入：新建一個結點他的指針域指向頭結點的頭地址，修改之后在將鏈表的頭地址指向新建結點的地址這樣新建結點就成為鏈表新的頭節點
**
對于鏈表中&head,一級指針，二級指針的總結
分析：
1，只要是修改頭指針則必須傳遞頭指針的地址，否則傳遞頭指針值即可(即頭指針本身)。這與普通變量類似，當需要修改普通變量的值，需傳遞其地址，否則傳遞普通變量的值即可(即這個變量的拷貝)。使用二級指針，很方便就修改了傳入的結點一級指針的值。 如果用一級指針，則只能通過指針修改指針所指內容，卻無法修改指針的值，也就是指針所指的內存塊。所以創建鏈表和銷毀鏈表需要二級指針或者一級指針引用。
2，不需要修改頭指針的地方用一級指針就可以了，比如插入，刪除，遍歷，清空結點。假如頭指針是L，則對L->next 及之后的結點指針只需要傳遞一級指針。
3，比如一個結點p，在函數里要修改p的指向就要用二級指針，如果只是修改p的next指向則用一級指針就可以了
~~~*以下代碼均是對于無表頭結點的操作*~
**
寫頭插時應該先想好代碼的思路：
創建結點元素
創建空鏈表
創建結點
插入節點函數
編譯鏈表
//創建結點元素
//創建空鏈表
//創建結點
//插入節點函數
//編譯鏈表
#include #includestruct node //構思結點元素
{
int num;
char name[20];
int age;
struct node * next;
};
typedef struct node Node;
typedef Node * Link;
void creat_list(Link * head) //創建鏈表初始化為空表
{
*head = NULL;
}
void is_malloc_ok(Link new_node) //判斷創建的結點是否成功分配了空間
{
if(NULL == new_node)
{
printf("malloc error!\n");
exit(-1);
}
}
void creat_new_node(Link * new_node)
{
*new_node = (Link)malloc(sizeof(Node));
is_malloc_ok(*new_node);
}
void display(Link head) //打印鏈表
{
Link p;
p = head;
if(NULL == head)
{
printf("Link is empty!\n");
return;
}
while(NULL != p)
{
printf("%d\n",p->num);
p = p->next;
}
}
void insert_node_head(Link * head,Link new_node)
{
new_node->next = *head; //通過圖2進行理解這里的地址轉換
*head = new_node;
}
int main()
{
int i = 0;
Link head = NULL; //初始化避野指針
Link new_node = NULL;
creat_list(&head); //**head是頭地址，對于鏈表創建是對于地址的操作，
因為鏈表名本身代表鏈表首地址，因此在調用函數操作傳入一個二階地址，
通過解引用(*head)來操作指針head**
for(i=0; i < 10; i++)
{
creat_new_node(&new_node);
new_node->num = i + 1;
insert_node_head(&head,new_node);
}
display(head);
return 0;
}
寫尾插法的代碼
void insert_node_tail(Link * head,Link new_node)
{
Link p; //尾插需要找到上一個結點的尾指針，因此需要一個變量定義此指針
p = *head;
if(NULL == *head) //鏈表為空時先插入第一個結點
{
*head = new_node;
new_node->next = NULL;
}
else //當P不為空時插入第二個結點
{
while(NULL != p->next)
{
p = p->next;
}
p->next = new_node; //尾插讓新結點的next都是NULL，頭指向上一個結點
new_node->next = NULL;
}
**
總結
由上面的例子以及比較，我們可以看見：
1、頭插法相對簡便，但插入的數據與插入的順序相反；
2、尾插法操作相對復雜，但插入的數據與插入順序相同。
**
隨機數倒敘排列
int insert_node_mid_sort(Link * head,Link new_node)
{
Link p,q;
p = q = *head;
if(NULL == *head) //空表時將第一個結點插入此時頭結點地址不為空
{
*head = new_node;
new_node->next = NULL;
}
else if((*head)->num > new_node->num) //當結點的num>頭結點時將他插入到頭結點前面
{
new_node->next = *head;
*head = new_node;
}
else
{
while(p != NULL && p->num < new_node->num) //參考下圖分析代碼 (&&有一個不滿足條件時就跳出代碼執行下面的代碼)
{
q = p;
p = p->next;
}
q->next = new_node;
new_node->next = p;
}
}
只需要將6的頭插入到5的尾，6的尾巴插入到7的頭就可以了。
while(p != NULL && p->num < new_node->num)
因為此時鏈表中已經有了結點，所以P不是NULL，切有num，此時5<6,
p,q,head,地址相同，此時p指向下一個結點
q = p;
p = p->next;
q->next = new_node;
new_node->next = p;
此時將new_node的頭地址，尾地址互換插入到鏈表中去，
**
將一個num添加到一個結點的前面
void insert_node_mid_front(Link * head,Link new_node,int loc)
{
Link p,q;
p = q = *head;
if((*head)->num == loc)
{
new_node->next = *head;
*head = new_node;
}
else
{
while(p != NULL && p->num != loc)
{
q = p;
p = p->next;
}
q->next = new_node;
new_node->next = p;
}
} //此代碼原理同上只是新建一個loc
#if//在主函數中打印
printf("\n\n");
create_node(&new_node);
new_node->num = 100;
printf("please input loc:\n");
scanf("%d",&loc);
insert_node_mid_front(&head,new_node,loc);
display(head);
刪除結點
void delete_node(Link * head,int num_del)
{
Link p, q;
p = q = *head;
if(NULL == *head)
{
printf("Link is empty!\n");
return;
}
else if((*head)->num == num_del)
{
*head = (*head)->next ;
free(p);
return;
}
else
{
while(NULL != p && p->num != num_del)
{
q = p;
p = p->next;
}
if(NULL == p)
{
printf("no such node!\n");
}
else
{
q->next = p->next;
free(p);
}
}
}
**
查找結點
Link search_node(Link head,int num_serch)
{
Link p;
p = head;
if(NULL == head)
{
printf("Link is empty!\n");
return NULL;
}
else
{
while( p != NULL && p->num != num_serch)
{
p = p->next;
}
if(NULL == p)
{
return NULL;
}
else
{
return p;
}
}
}
**
對于如何使用1級指針或者2級指針參考博客
待續…
總結
以上是生活随笔為你收集整理的c语言中头结点不为零怎么写,C语言不带表头结点的单链表操作的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c语言程序朴素贝叶斯分类器,生成式学习算
- 下一篇： 用c语言求解n阶线性矩阵方程组,用C语言