链表 – 数据结构
最后更新于：2022-04-01 20:05:52
关于头结点，一般链表都会有头结点，他会有几个好处：
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 && jnext;
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");
}
~~~
';