不带头结点的单链表------C语言实现(带注释)

蔚落 2023-10-18 13:46 82阅读 0赞

\#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;  
\}