数据结构1-G

数据结构第一次作业之双链表G

代码下载

点击下载源代码

代码展示

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

/*
该链表所能存放的数为int整型（-32768~32767之间的整数）
*/

#define MAXSIZE 100//顺序表最大长度



/*定义顺序表*/
typedef struct Node
{
	int num;
	int length;
	struct Node *next;
	struct Node *prev;
}*LNode;

void CreateList(LNode *node)
{
    int number;
    LNode p = node;
    LNode head = node;
    printf("请输入您需要输入的数据的个数\n");
    number = IsDataNum();
    for(int i = 1; i <= number-1; i++){
        printf("请输入第%d个节点的数：\n",i);
        p->num = IsDataNum();
        p->next = (LNode *)malloc(sizeof(LNode));
        p->next->prev = p;
        p = p->next;
    }
    head->length = number;
    printf("请输入第%d个节点的数：\n",number);
    p->num = IsDataNum();
    p->next = NULL;
}

void PrintList(LNode *node)
{
    LNode p = node;
    int num = 1;
    while(p!=NULL){
        printf("第%d个节点的值为：%d\n",num,p->num);
        p = p->next;
        num++;
    }
}

void DeletePositionList(LNode *node,int num)
{
    LNode p = node;
    LNode head = node;
    for (int i = 1; i <= num-1; i++){
        p = p->next;
    }
    if (num != head->length){
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    else{
        p->prev->next = NULL;
    }

    free(p);
}

void DeleteSameList(LNode *node)
{
    LNode p,head,q;
    q = node;
    p = node;
    head = node;
    while(p != NULL){
        q = p->next;
        while(q != NULL){
            if(p->num == q->num){
                if(q->next != NULL){
                    LNode ql = q;
                    q = q->prev;
                    ql->prev->next = ql->next;
                    ql->next->prev = ql->prev;
                    free(ql);
                    head->length--;
                }
                else{
                    q->prev->next = NULL;
                    q = NULL;
                    free(q);
                    head->length--;
                    break;
                }
            }
            q = q->next;
        }
        p = p->next;
    }

    PrintList(node);

}

void DeleteKeyList(LNode *node)
{
    printf("请输入删除的Key值：\n");
    int number = IsDataNum();

    LNode p = node;
    while(p != NULL){
        if(p->num == number){
            if(p->next != NULL && p != node){//判断是否为最后一个节点
                LNode q = p;
                p->next->prev = p->prev;
                p = p->next;
                p->prev->next = p;
                p = p->prev;
                free(q);
            }
            else if(p != node){
                p->prev->next = NULL;
                p = NULL;
                free(p);
                break;
            }
            else{
                node = p->next;
            }

        }
        p = p->next;
    }

    PrintList(node);
}

void AddList(LNode *node)
{
    printf("写完发现是单链表，我G了，不想写了，你看着办吧！");

}

void ExitList(LNode *node)
{
    LNode p = node;
    while(p->next != NULL){
        p = p->next;
        free(p->prev);
    }
    free(p);
    printf("已经成功释放所有的空间");
    getchar();
    exit(1);
}

int IsLengthNum(LNode *node)
{
    char ch[10];
    LNode p = node;
    scanf("%s",ch);
    int i = 1;
    while(ch[i-1]!='\0'){
        if(ch[i-1] < '0' || ch[i-1] > '9'){
            printf("输入格式错误\n");
            printf("请0~%d之内的整数：",p->length);
            scanf("%s", ch);
            i = 1;
        }
        else{
            i++;
        }
    }

    int number = atoi(ch);

    return number;
}

void Menu(LNode *node)
{
    char ch[10];
    scanf("%s",ch);
    while(ch[1]!='\0' || ch[0] <= '0' || ch[0] >= '6'){
        printf("请键入1~5的整数");
        scanf("%s",ch);
    }
    switch (ch[0])
    {
    case '1':
        DeleteSameList(node);
        break;
    case '2':
        DeleteKeyList(node);
        break;
    case '3':
        AddList(node);
        break;
    case '4':
        printf("请输入想删除的节点位置\n");
        DeletePositionList(node,IsLengthNum(node));
        PrintList(node);
        break;
    case '5':
        ExitList(node);
        break;
    }
}

//获取一个整形，并判断该整形是否合法
int IsDataNum()
{
    char ch[10];
    scanf("%s",ch);
    int i = 1;
    while(ch[i-1]!='\0'){
        if(ch[i-1] < '0' || ch[i-1] > '9'){
            printf("输入格式错误\n");
            printf("请输入-32768~32767之间的整数：");
            scanf("%s", ch);
            i = 1;
        }
        else{
            i++;
        }
    }

    int number = atoi(ch);
    return number;
}

int main()
{
    LNode *node = NULL;
    node = (LNode *)malloc(sizeof(LNode));

    CreateList(node);//创建链表

    PrintList(node);//打印链表

    printf("您已成功创建链表\n*******************************************\n");
    printf("请输入你想进行的操作\n");
    printf("1:删除重复的节点\n");
    printf("2:删除节点中所有的key值\n");
    printf("3:插入一个数\n");
    printf("4:删除某个节点的数据\n");
    printf("5:退出程序\n");

    Menu(node);



}