c语言—链表总结

一.单链表

自己总结了一下单向链表逆序，排序，查找倒数第n个结点的知识

struct student
{
   
    char name[20];
    int number;
    struct student *next;
};

排序—交换分为两步，先交换结点，后交换指针

struct student *linksort(struct student *pHead)
{
   
    struct student *p = NULL;
    struct student *q = NULL;
    struct student *r = NULL;
    struct student n;
    for(p = pHead; p; p = p->next)
    {
   
        for(q = p->next; q; q = q->next)
        {
   
            if(p->number > q->number)
            {
   
                n = *p;
                *p = *q;
                *q = n;
                r = p->next;
                p->next = q->next;
                q->next = r;
            }
        }
    }
    return pHead;
}

查找倒数第n个结点

void find(struct student *pHead, int n)
{
   
    struct student *p,*q;
    p = q = pHead;
    int m = n;
    while(pHead == NULL || n < 0)
        return;
    //重点
    while(n > 0)
    {
   
        p = p->next;
        n--;
    }
    
    while(p)
    {
   
        p = p->next;
        q = q->next;
    }
    printf("倒数第%d个结点信息: \n",m);
    printf("姓名:%s\n",q->name);
    printf("学号:%d\n",q->number);
}

逆序—创建一个新链

struct student *inversion(struct student *pHead)
{
   
    struct student *pTemp,*q;
    pTemp = NULL;
    while(pHead)
    {
   
        q = pHead->next;
        pHead->next = pTemp;
        pTemp = pHead;
        pHead = q;
    }
    return pTemp;
}

逆序2—递归实现
递归终止条件为链表只剩一个结点时，返回次结点的指针

struct student *inversion2(struct student *pHead)
{
   
	struct student *pTemp = NULL;
	if(pHead == NULL || pHead->next == NULL)
		return pHead;
	pTemp = inversion2(pHead->next);//递归
	pHead->next->next = pHead;	//回溯
	pHead->next = NULL;
	return pTemp;

}

循环链表

循环链表其实和单链表差别不大，主要是尾指针的指向

typedef struct _node
{
   
    int data;
    struct _node *next;
}Node;

int count = 0;//结点数

创建结点

Node *create(Node *pHead)	//创建结点
{
   
    Node *pEnd,*pNew;
    int n;
    int i;
    printf("创建几个节点: ");
    scanf("%d",&n);
    for(i = 0; i < n; i++)
    {
   
        pNew = (Node *)malloc(sizeof(Node));
        printf("输入:");
        scanf("%d",&pNew->data);
        pNew->next = NULL;
        if(pHead == NULL)
            pHead = pNew;
        else
            pEnd->next = pNew;
        pEnd = pNew;
        count++;
    }
    pEnd->next = pHead;
    return pHead;
}

遍历链表

void print(Node *pHead)     //遍历
{
   
    Node *pTemp = pHead;
    int n = count * 2;
    int i = 0;
    printf("打印: \n");
    while(pTemp)
    {
   
        i++;
        printf("%d\t",pTemp->data);
        pTemp = pTemp->next;
        if(i == n)
            break;
    }
}

双向链表

如果理解了单链表，双向链表也不是什么难事了

typedef struct _node
{
   
    int data;
    struct _node *pre;
    struct _node *next;
}Node;

int count = 0;  //结点数

创建双向链表

Node *Create(Node *pHead)  //创建双向链表
{
   
    Node *pEnd,*pNew;
    int n;
    int i;
    printf("创建几个结点: ");
    scanf("%d",&n);
    for(i = 0; i < n; i++)
    {
   
        count++;
        pNew = (Node *)malloc(sizeof(Node));
        printf("输入: ");
        scanf("%d",&pNew->data);
        pNew->next = NULL;
        if(pHead == NULL)
        {
   
            pNew->pre = NULL;
            pHead = pNew;
        }
        else
        {
   
            pEnd->next = pNew;
            pNew->pre = pEnd;
        }
        pEnd = pNew;
    }
    return pHead;
}

遍历

void print(Node *pHead)     //遍历
{
   
    Node *pTemp = pHead;
    Node *p = pHead;
    printf("打印: \n");
    //从左开始遍历
    while(pTemp)
    {
   
        printf("%d\t",pTemp->data);
        pTemp = pTemp->next;
    }
//遍历到链表尾
    while(p && p->next != NULL)
        p = p->next;
    printf("\n");
    //从右开始遍历
    while(p)
    {
   
        printf("%d\t",p->data);
        p = p->pre;
    }
}

!@#$%^&*~