不带头结点的单链表------C语言实现(带注释)
#include <stdio.h>
#include <stdlib.h>
/*next 英文詞的意思 是 “下一個”。
鏈表里 用于 指向下一個節點的指針，也就是指向下一個（節點）結構類型的指針。
struct node {} 是一種結構，有兩個成員，一個成員是 int 數據，另一個是指向下一個 node 結構的指針。
next 是變量名字，你當然也可以改用別的名字例如：
struct node {int d; struct node *xyg;};
用漢語拼音 xyg 替代 next。*/
/* *next是鏈表節點指向下一個節點的指針，用來存放下一個節點的地址域
這是鏈表的一種固定結構*/
//第一個星號是指針域,指向下一個節點地址,第二個星號就是struct 類型的指針啊！加了就是指針型，不加就是一個對象
你應該是在學單鏈表吧，我猜你的結構體可能寫錯了，附上我的猜測，若沒錯請@一下
//typedef struct LNode{ ? ?//此行的LNode是一個結構標簽
// ? ?ElemType data;
// ? ? ? ?struct LNode *next;?
// ? ? ? ? ? ?}LNode,*LinkList; ? ?//此行的LNode是結構體struct LNode的一個別名
// ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //*LinkList也是結構體struct LNode的一個別名
// ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //換言之LinkList是結構體struct LNode類型的指針的別名
// ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //也就是說 ?struct LNode *p;這條語句等同于LinkList p;
//typedef struct LNode{
// ? ElemType data;
// ? struct LNode next; }LNode,*LinkList;
// ? 其中第一個LNode是定義的結構體數據結構類型名，第二個LNode是定義結構體的別名，而LinkList是指向該結構體變量的指針
typedef struct node
{
? ? int id;
? ? struct node * next;
}* Link, Node;
/*創建鏈表*/
void create_link(Link * head)
{
? ? *head = NULL;//空鏈表
}
/*頭插*/
void insert_node_head(Link * head, Link new_node)
{
? ? new_node->next = *head;
? ? *head = new_node;
}
#if 1
/*尾插*/
void insert_node_tail(Link * head, Link new_node)
{
? ? Link p = NULL;
? ? if (*head == NULL)
? ? {
? ? ? ? *head =new_node;
? ? ? ? new_node->next = NULL;
? ? ? ? return ;
? ? }
? ? else
? ? {
? ? ? ? p = *head;
? ? ? ? while (p->next != NULL)
? ? ? ? {
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? p->next = new_node;
? ? ? ? new_node->next = NULL;
? ? }
}
#endif
/*輸出鏈表*/
void display_link(Link head)
{
? ? Link p = NULL;
? ? p = head;
? ? if(p == NULL)
? ? {
? ? ? ? printf("link is empty!\n");
? ? ? ? return ;
? ? }
? ? while (p != NULL)
? ? {
? ? ? ? printf("id = %d\n", p->id);
? ? ? ? p = p->next;
? ? }
/*
putchar 描述
C 庫函數 int putchar(int char) 把參數 char 指定的字符（一個無符號字符）寫入到標準輸出 stdout 中。
聲明
下面是 putchar() 函數的聲明。
int putchar(int char)
參數
char -- 這是要被寫入的字符。該字符以其對應的 int 值進行傳遞。
返回值
該函數以無符號 char 強制轉換為 int 的形式返回寫入的字符，如果發生錯誤則返回 EOF。
*/
? ? putchar(10);
}
/*檢查malloc是否分配成功*/
void is_malloc_ok(Link new_node)
{
? ? if (new_node == NULL)
? ? {
? ? ? ? printf("malloc error!\n");
? ? ? ? exit(-1);
? ? }
}
/*創建節點*/
void create_node(Link * new_node)
{
/*malloc 描述
C 庫函數 void *malloc(size_t size) 分配所需的內存空間，并返回一個指向它的指針。
聲明
下面是 malloc() 函數的聲明。
void *malloc(size_t size)
參數
size -- 內存塊的大小，以字節為單位。
返回值
該函數返回一個指針 ，指向已分配大小的內存。如果請求失敗，則返回 NULL。*/
? ? //sizeof 指針本身所占據的內存區
? ? *new_node = (Link)malloc(sizeof(Node));
? ? //is_malloc_ok 函數
? ? is_malloc_ok(*new_node);
}
/*釋放節點*/
void realse_node(Link * head)
{
? ? Link p = NULL;
? ? p = *head;
? ? while (*head != NULL)
? ? {
? ? ? ? *head = (*head)->next;//head移動
? ? ? ? free(p);//釋放head之前的節點
? ? ? ? p = *head;
? ? }
}
/*中間插入節點*/
void insert_node_mid(Link * head, Link new_node, int loc)
{
? ? int i;
? ? Link p = NULL;
? ? p = *head;
? ? for(i = 1; i < loc; i++)
? ? {
? ? ? ? p = p->next;
? ? }
? ? new_node->next = p->next;
? ? p->next = new_node;
}
/*中間插入，前面*/
void insert_node_mid_front(Link * head, Link new_node)
{
? ? Link p = NULL, q = NULL;
? ? p = q = *head;
? ? if (*head == NULL)
? ? {
? ? ? ? printf("link is empty\n");
? ? ? ? return ;
? ? }
? ? while (p != NULL && p->id != new_node->id)
? ? {
? ? ? ? q = p;
? ? ? ? p = p->next;
? ? }
? ??
? ? if (p == NULL)
? ? {
? ? ? ? printf("No such node in link!\n");
? ? ? ? free(new_node);
? ? ? ? return ;
? ? }
? ? if (p->id == (*head)->id)
? ? {
? ? ? ? new_node->next = *head;
? ? ? ? *head = new_node;
? ? }
? ? else
? ? {
? ? ? ? q->next = new_node;
? ? ? ? new_node->next = p;
? ? }
}
#if 1
/*刪除節點*/
void delete_node(Link * head, int data)
{
? ? Link p = NULL, q = NULL;
? ? q = p = *head;
? ? if (p == NULL)//鏈表為空的時候
? ? {
? ? ? ? printf("link is empty!\n");
? ? ? ? return ;
? ? }
? ? else//鏈表不為空的時候
? ? {
? ? ? ? while (p != NULL && p->id != data)//尋找節點
? ? ? ? {
? ? ? ? ? ? q = p;
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? if ((*head)->id == data)//刪除節點為頭節點時
? ? ? ? {
? ? ? ? ? ? *head = (*head)->next;
? ? ? ? ? ? free(p);//free(q);
? ? ? ? }
? ? ? ? else//刪除節點不為頭節點，尾節點不用考慮
? ? ? ? {
? ? ? ? ? ? q->next = p->next;
? ? ? ? ? ? free(p);
? ? ? ? }
? ? }
}
#endif
#if 0
void delete_node(Link * head, int data)
{
? ? Link p = NULL, q = NULL;
? ? q = p = *head;
? ? if (p == NULL)//鏈表為空的時候
? ? {
? ? ? ? printf("link is empty!\n");
? ? ? ? return ;
? ? }
? ? else//鏈表不為空的時候
? ? {
? ? ? ? while (p != NULL && (p->next)->id != data)//尋找節點
? ? ? ? {
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? if ((*head)->id == data)//刪除節點為頭節點時
? ? ? ? {
? ? ? ? ? ? *head = (*head)->next;
? ? ? ? ? ? free(p);//free(q);
? ? ? ? }
? ? ? ? else//刪除節點不為頭節點，尾節點不用考慮
? ? ? ? {
? ? ? ? ? ? q = p->next;
? ? ? ? ? ? p->next = q->next;
? ? ? ? ? ? free(q);
? ? ? ? }
? ? }
}
#endif
/*插入之后依舊有序*/
void insert_node_seq(Link * head, Link new_node)
{
? ? Link p = NULL, q = NULL;
? ? p = q = *head;
? ? if (p == NULL)//鏈表為空的時候
? ? {
? ? ? ? *head = new_node;
? ? ? ? new_node->next = NULL;
? ? }
? ? else
? ? {
? ? ? ? //printf("ids = %d\n", p->id); //上一次插入的數據
? ? ? ? //printf("newid = %d\n", new_node->id); //下一次插入的數據
? ? ? ? //printf("ids = %d\n", p); //154357768 148934664
? ? ? ? while (p != NULL && p->id < new_node->id)//尋找位置
? ? ? ? {
? ? ? ? ? ? q = p;
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? //printf("hids = %d\n",(*head)->id); //上一次插入的數據
? ? ? ? //printf("nids = %d\n",new_node->id); //下一次插入的數據
? ? ? ? if ((*head)->id > new_node->id)//找到的節點為頭節點
? ? ? ? {
? ? ? ? ? ? new_node->next = *head;
? ? ? ? ? ? *head = new_node;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? q->next = new_node;
? ? ? ? ? ? new_node->next = p;
? ? ? ? }
? ? }
}
#if 1
/*插入依舊有序實現方法二*/
void insert_node_seq_1(Link * head, Link new_node)
{
? ? Link p = NULL;
? ? Link q = NULL;
? ? p = q = *head;
? ? if (p == NULL)//空鏈表
? ? {
? ? ? ? *head = new_node;
? ? ? ? new_node->next =NULL;
? ? }
? ? else
? ? {
? ? ? ? while ((p->id < new_node->id) && (p->next != NULL))
? ? ? ? {
? ? ? ? ? ? q = p;
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ??
? ? ? ? if ((*head)->next == NULL)//一個節點的時候
? ? ? ? {
? ? ? ? ? ? if (p->id > new_node->id)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? new_node->next = *head;
? ? ? ? ? ? ? ? *head = new_node;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p->next = new_node;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if (p->next == NULL)//尾節點
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (p->id > new_node->id)//插入前
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? q->next = new_node;
? ? ? ? ? ? ? ? ? ? new_node->next = p;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? p->next = new_node;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? else//不是尾節點
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if((*head)->id > new_node->id)//頭節點
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? new_node->next = *head;
? ? ? ? ? ? ? ? ? ? *head = new_node;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else//中間插入時
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? q->next = new_node;
? ? ? ? ? ? ? ? ? ? new_node->next = p;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }/*end of if()*/
? ? }/*end of if (p == NULL)*/
}
#endif
int main()
{
? ? Link head = NULL;//防止出現野指針
? ? Link new_node = NULL;//防止出現野指針
? ? int i;
? ? int data;
? ? create_link(&head);//創建鏈表
? ? for (i = 0; i < 10; i++)//值域賦值，并插入新節點
? ? {
? ? // ? ?new_node = (Link)malloc(sizeof(Node));//創建新節點
? ? //create_node 創建節點
? ? ? ? create_node(&new_node);
? ? // ? ?new_node->id = i + 1;//賦值
? ? // ? ?insert_node_head(&head, new_node);//插入節點，頭插
? ? // ? ?insert_node_tail(&head, new_node);//插入節點，尾插
? ??
? ? ? ? printf("please input node value:\n");
? ? ? ? scanf("%d", &new_node->id);
? ? ? ? insert_node_seq(&head, new_node);
// ? ? ? ?insert_node_seq_1(&head, new_node);
? ? ? ? display_link(head);//輸出節點的值域
? ? }
? ? display_link(head);//輸出節點的值域
#if 0
? ? create_node(&new_node);
? ? new_node->id = i + 1;
? ? insert_node_mid(&head, new_node, 3);//指定位置插入，中間插入
? ? putchar(10);
? ? display_link(head);//輸出節點的值域
#if 0
? ? create_node(&new_node);
? ? scanf("%d", &new_node->id);
? ? insert_node_mid_front(&head, new_node);
? ? display_link(head);//輸出節點的值域
#endif
? ? scanf("%d", &i);
? ? delete_node(&head, i);//刪除指定節點
? ? display_link(head);
#if 0
? ? create_node(&new_node);
? ? scanf("%d", &new_node->id);
? ? insert_node_seq(&head, new_node);//有序插入指定元素
? ? display_link(head);
#endif
#endif
? ? realse_node(&head);//釋放節點
? ? display_link(head);//輸出節點的值域
? ? return 0;
}
?
總結
以上是生活随笔為你收集整理的不带头结点的单链表------C语言实现(带注释)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 不带头结点的单链表------C语言实现
- 下一篇： 艋舺电影片段（锰钾）