链表功能的实现

数据结构与算法分析

// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。
/************************************************************************/
/*             以下是关于线性表链接存储（单链表）操作的18种算法        */
/* 1.初始化线性表，即置单链表的表头指针为空 */
/* 2.创建线性表，此函数输入负数终止读取数据*/
/* 3.打印链表，链表的遍历*/
/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
/* 5.返回单链表的长度 */
/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
/* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
/* 10.向单链表的表头插入一个元素 */
/* 11.向单链表的末尾添加一个元素 */
/* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
/* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
/* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
/* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
/* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
/* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */
/*其中19，18， 13，8因为时间关系还没有实现*/
/************************************************************************/
#include<stdio.h>
#include "stdafx.h"
#include<stdlib.h>
typedef int elementtype;
typedef struct node *ptrtonode;
typedef ptrtonode list;
typedef ptrtonode position;
typedef struct node{
    elementtype element;
    position next;
}node;
node* NewLinkedlist(void);/* 2.创建线性表，此函数输入负数终止读取数据*/
void FreeLinkedlist(node *);/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
void PrintfLinkedlist(node *);/* 3.打印链表，链表的遍历*/
int CountLinkedlist(node *);/* 5.返回单链表的长度 */
int EmptyLinkedlist(node *);/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
int CheckLinkedlist(node *);/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
node* InsertLinkedlist(node *);/*10-12.向单项链表中第pos个节点插入元素，pos=0则从表头插入，pos>0则从表中插入 */
int ChangeLinkedlist(node*);/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
node* DeletLinkedlist(node*);/*14-16 删除链表的第pos个节点元素，返回链表表头的地址*/
int main()
{
    node *p1;
    p1=NewLinkedlist();/* 2.创建线性表，此函数输入负数终止读取数据*/
    EmptyLinkedlist(p1);/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
    PrintfLinkedlist(p1);/* 3.打印链表，链表的遍历*/
    CountLinkedlist(p1);/* 5.返回单链表的长度 */
    CheckLinkedlist(p1);/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
    p1=InsertLinkedlist(p1);/*8-10.向单项链表中第pos个节点插入元素，pos=0则从表头插入，pos>0则从表中插入 */
    p1 = DeletLinkedlist(p1);/*14-16 删除链表的第pos个节点元素，返回链表表头的地址*/
    ChangeLinkedlist(p1);/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
    FreeLinkedlist(p1);/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
    while(getchar()=='\n');
    getchar();
    return 0;
}
node* NewLinkedlist(void)/* 2.创建线性表，此函数输入负数终止读取数据*/
{
    node *p1, *p2,*p3;
    p1 = p2 =p3= (node*)malloc(sizeof(node));
    if (p1 == NULL)
        printf("Fail to get the memory!\n");
    while (p1 != NULL)
    {
        scanf_s("%d", &p1->element);
        if (p1->element<0)
        {
            printf("Over\n");
            p2->next = NULL;
            break;
        }   
        else
        {
            p2 = p1;
            p1 = p1->next = ((node*)malloc(sizeof(node)));
        }
        if (p1 == NULL)
            printf("Fail to get the memory!\n");
    }
    return p3;
}
void PrintfLinkedlist(node *p1)/* 3.打印链表，链表的遍历*/
{
    while (p1->next != NULL)
    {
        printf("%d | ", p1->element);
        p1 = p1->next;
    }
    if(p1->element>0)
    printf("%d |\n", p1->element);
    printf("Complete!\n");
}
void FreeLinkedlist(node *p1)/* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
{
    node *p2 = p1;
        while (p2 != NULL )
        {
            p2 = p2->next;
            free(p1);
            p1 = p2;
        }
        free(p2);
        printf("Clear!\n");
}
int CountLinkedlist(node *p1)/* 5.返回单链表的长度 */
{
    int n = 0;
    while (p1 != NULL && p1->element>0)
    {
        n++;
        p1 = p1->next;
    }
    printf("The Linkedlist has %d nodes\n", n);
    return n;
}
int EmptyLinkedlist(node *p1)/* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
{
    if (p1->next == NULL && p1->element<0)
    {
        printf("This is an empty linkedlist\n");
        return 0;
    }
    else
    {
        printf("This is not an empty linkedlist\n");
        return 1; 
    }
}
int CheckLinkedlist(node *p1)/* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
{
    int n,i=0;
    node *p2=p1;
    printf("Please insert the node you want to check:");
    scanf_s("%d", &n);
    while (i < n &&p2!=NULL)
    {
        i++;
        p1 = p2;
        p2 = p2->next;
    }
    if (i == n)
        printf("The %d node is %d.\n", n, p1->element);
    else
        printf("Out of the range of your linkedlist\n");
    return p1 -> element;
    }
node* InsertLinkedlist(node* p1)/*10-12.向单项链表中第pos个节点插入元素，pos=0则从表头插入，pos>0则从表中插入 */
{
    int pos, n,i=1;
    node *p2,*p3;
    p3 = p1;
    printf("Please insert the pos of the node:");
    scanf_s("%d",&pos);
    printf("Please insert the element of the node:");
    scanf_s("%d", &n);
    p2 = (node*)malloc(sizeof(node));
    p2->element = n;
    p2->next = NULL;
    if (pos == 0)
    {
        p2->next = p1;
    }
    else
    {
        while (i < pos && p1->next != NULL)
        {
            i++;
            p1 = p1->next;
        }
        if (i == pos)
        {
            if (p1->next != NULL)
                p2->next = p1->next->next;
            p1->next = p2;
        }
        else
            printf("Out of the range of your linkedlist\n");
        p2 = p3;
    }
    PrintfLinkedlist(p2);
    return p2;
}
int ChangeLinkedlist(node *p1)/* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
{
    int pos, n, i = 1;
    node *p3;
    p3 = p1;
    printf("Please insert the pos of the node:");
    scanf_s("%d", &pos);
    printf("Please insert the element of the node:");
    scanf_s("%d", &n);
    while (i < pos && p1->next != NULL)
    {
        i++;
        p1 = p1->next;
    }
    if (i == pos)
    {
        p1->element = n;
    }
    else
    {
        printf("Out of the range of your linkedlist\n");
        return 0;
    }
    PrintfLinkedlist(p3);
    return 1;
}
node* DeletLinkedlist(node *p1)/*14-16 删除链表的第pos个节点元素，返回链表表头的地址*/
{
    int pos, i = 2;
    node *p2,*p3;
    p3=p2 = p1;
    printf("Please insert the pos of the node you want to delet:");
    scanf_s("%d", &pos);
    if (pos == 1)
    {
        p1 = p1->next;
        free(p1);
    }
    while (i < pos && p1->next != NULL)
    {
        i++;
        p1 = p1->next;
    }
    if (i == pos)
    {
        p2 = p1->next;
        if (p1->next->next != NULL)
            p1->next = p1->next->next;
        else
            p1->next = NULL;
        free(p2);
    }
    else
    {
        printf("Out of the range of your linkedlist\n");
        return 0;
    }
    PrintfLinkedlist(p3);
    return p3;
 }