Question

如何用C语言编写一个链表？

Answer 1

可以用结构体和指针来实现

定义：

定义一个单个元素的结构

typedef struct Chain_tag { // 这里用typedef来定义，方便使用
    int data; // 这里的数据可以是任意类型
    //其他数据
    struct Chain_tag *prev, *next;// 由于Chain为不完全类型，故只能用指针的方式声明
} Chain;

使用：

用单个结构体的指针作为head

#include <malloc.h>

//Chain的定义写在这里

Chain *
alloc_single_chain(int data /*, （其他参数）*/)
{
    Chain *tmp;
    
    tmp = malloc(sizeof(Chain));
    tmp.data = data;
    //...其余数据初始化
    tmp.prev = tmp.next = NULL; // 将前后指针置为NULL
    
    return tmp;
}

void
dispose_chain(Chain *target) //其实这里功能简单，用宏实现也可以
{
    free(target);
    return;
}

int main()
{
    Chain *head;
    Chain *pos;
    
    head = alloc_single_chain(10);//初始化起始结点
    head->next = alloc_single_chain(11);//同理。。下一个结点
    
    for (pos = head; pos; pos = pos->next)//清理垃圾好习惯
    {
       dispose_chain(pos);
    }
    
    return 0;
}

这里有几点要注意：

1. 由于链表用指针来实现，故不要忘记分配内存

2. 垃圾清理时一定要从起始结点开始依次向后释放，以防内存泄漏
   

Answer 2

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

struct Node
{
int data;//数据域
struct Node * next;//指针域
};

/*************************************************************************************
　　*函数名称:Create
　　*函数功能:创建链表.
　　*输入:各节点的data
　　*返回值:指针head
*************************************************************************************/
struct Node * Create()
{
struct Node *head,*p1,*p2;
head = NULL;
p1 = p2 = (struct Node *)malloc(sizeof(struct Node));
printf("Input the linklist (Input 0 to stop):\n");
scanf("%d",&p1->data);
while(p1->data!=0)
{
if(head == NULL){
head = p1;
}else{
p2->next = p1;
p2 =p1;
}
p1 = (struct Node *)malloc(sizeof(struct Node));
scanf("%d",&p1->data);
}
p2->next = NULL;
return head;
}
/*************************************************************************************
　　*函数名称:insert
　　*函数功能:在链表中插入元素.
　　*输入:head 链表头指针,p新元素插入位置,x 新元素中的数据域内容
　　*返回值:无
*************************************************************************************/
void insert(struct Node * head,int p,int x)
{
struct Node * tmp = head;
struct Node * tmp2 ;
int i ;
for(i = 0;i<p;i++)
{
if(tmp == NULL)
return ;
if(i<p-1)
tmp = tmp->next;
}
tmp2 = (struct Node *)malloc(sizeof(struct Node));
tmp2->data = x;
tmp2->next = tmp->next;
tmp->next = tmp2;
}
/**************************************************************************************
　　*函数名称：del
　　*函数功能:删除链表中的元素
　　*输入:head 链表头指针,p 被删除元素位置
　　*返回值:被删除元素中的数据域.如果删除失败返回-1
**************************************************************************************/
int del(struct Node * head,int p)
{
struct Node * tmp = head;
int ret , i;
for(i = 0;i<p;i++)
{
if(tmp == NULL)
return -1;
if(i<p-1)
tmp = tmp->next;
}
ret = tmp->next->data;
tmp->next = tmp->next->next;
return ret;
}
/**************************************************************************************
　　*函数名称：print
　　*函数功能:打印链表中的元素
　　*输入:head 链表头指针
　　*返回值:无
**************************************************************************************/
void print(struct Node *head)
{
struct Node *tmp;
for(tmp = head; tmp!=NULL; tmp = tmp->next)
printf("%d ",tmp->data);
printf("\n");
}
/**************************************************************************************
　　*函数名称：main
　　*函数功能:主函数创建链表并打印链表。
**************************************************************************************/
int main(){
struct Node * head = Create();
print(head);
return 0;
}

Answer 3

#include <stdio.h>
#include <stdlib.h.>

typedef int ElemType;

typedef struct node {
int data;
struct node *prior,*next;
} *SqList;

SqList CreateList1(int n) { // 创建单向循环链表
SqList head,p,q;
head = p = (SqList)malloc(sizeof(node));
for(int i = 0;i < n;i++) {
q = (SqList)malloc(sizeof(node));
q->data = 2*i + 1;
p->next = q;
p = q;
}
p->next = head;
return head;
}

SqList CreateList2(int n) { // 创建单向非循环链表
SqList head,p,q;
head = p = (SqList)malloc(sizeof(node));
for(int i = 0;i < n;i++) {
q = (SqList)malloc(sizeof(node));
q->data = 2*(i + 1);
p->next = q;
p = q;
}
p->next = NULL;
return head;
}

void ChangeList1(SqList head) { // 单向循环链表改为双向循环链表
SqList p,q;
p = head;
q = p->next;
while(q != head) {
q->prior = p;
p = q;
q = q->next;
}
head->prior = q;
}

void ChangeList2(SqList head) { // 单向非循环链表改为双向循环链表
SqList p,q;
p = head;
q = p->next;
while(q != NULL) {
q->prior = p;
p = q;
q = q->next;
}
p->next = head;
head->prior = p;
}

void PrintList1(SqList head) { // 顺向打印非循环链表数据
SqList p = head->next;
while(p != NULL) {
printf("%3d",p->data);
p = p->next;
}
printf("\n\n");
}

void PrintList2(SqList head) { // 反向打印循环链表数据
SqList p = head->prior;
while(p != head) {
printf("%3d",p->data);
p = p->prior;
}
printf("\n\n");
}

void FreeList(SqList head) {
SqList p,q;
p = head;
q = p->next;
while(q != head) {
p = q;
q = p->next;
free(p);
}
free(head);
}

int main() {
SqList head = CreateList2(10); // head为非循环链表
PrintList1(head); // 顺向打印非循环链表
ChangeList2(head);
PrintList2(head);
FreeList(head);
return 0;
}