DS1:头插法建立单链表
头插法从一个空表开始，读取数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。简单来说，就是把新加进的元素放在表头后的第一个位置：
- 先让新节点的next指向头节点之后；
- 然后让表头的next指向新节点。
比如学校食堂吃饭排了一大队人，你一上来就插到头一个，那么打饭师傅面对的NEXT就是你了，你的下一个就是原来的队头，队头的上一个就是你。
方法一：
#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node{
datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
listnode *p;
linklist createlist(){
char ch;
linklist head;
listnode *p;
head=NULL;/*初始化为空*/
ch=getchar();/*传入键盘的字符*/
while (ch!='\n'){
p=(listnode*)malloc(sizeof(listnode));/*分配空间*/
p->data=ch;/*数据域赋值*/
p->next=head;/*指定后继指针*/
head=p;/*head指针指定到新插入的结点上*/
ch=getchar();
}//while
return (head);
}
main(){
linklist newlist=createlist();
do
{
printf("%c\n",newlist->data);
newlist=newlist->next;
}while(newlist!=NULL);
printf("\n");
}//main
方法二：
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node * next;
};
//建立只含头结点的空链表
struct node * create_list()
{
struct node * head = NULL;
head = (struct node *)malloc(sizeof(struct node));
if (NULL == head)
{
printf("memory out of use\n");
return NULL;
}
head->next = NULL;
head->data = 0;
return head;
}
//头插法建立链表
int insert_form_head(struct node * head, int num)
{
struct node * head_t = head->next;
struct node * new_node = NULL;
new_node = (struct node *)malloc(sizeof(struct node));
if (NULL == new_node)
{
printf("memory out of use\n");
return -1;
}
//将新结点插入到链表的最后
new_node->data = num;
new_node->next = head_t;
head->next = new_node;
return 0;
}
//打印链表
int show_list(struct node * head)
{
struct node * temp;
temp = head->next;
while(temp)
{
printf("%d\n",temp->data);
temp = temp->next;
}
return 0;
}
// 按值删除结点，头结点不被删除
int delete_node(struct node *head, int data)
{
//head_t 保存要删除结点的上一个结点
struct node * head_t = head;
struct node * temp = NULL;
if (head == NULL)
{
printf("delete node from empty list!\n");
return -1;
}
//查找删除的结点的前一个结点
//如果此处查找的是删除的结点，则需要另加一个指针保存删除结点的前一个指针
while(NULL != head_t->next)
{
if (data == head_t->next->data)
break;
head_t = head_t->next;
}
//如果要删除的结点不存在，直接返回
if (NULL==head_t->next)
{
printf("node not found\n");
return -1;
}
//删除操作
temp = head_t->next;
head_t->next = head_t->next->next;
free(temp);
return 0;
}
int main(int argc, char* argv[])
{
struct node * head;
head = create_list();
if (NULL == head)
printf("create_list error\n");
insert_form_head(head,123);
insert_form_head(head,456);
show_list(head);
printf("delete once!\n");
delete_node(head,123);
show_list(head);
printf("delete second!\n");//以下是调试代码
delete_node(head,456);
show_list(head);
delete_node(head,0);
show_list(head);
}