[数据结构与算法]数据结构第二章相关链表

单链表

#include <iostream>

using namespace std;
typedef struct node{
    int data;
    struct node *next;
}list1,*list2;
bool initlist(list2 &first)//链表初始化
{
    first=new list1;
    first->next=NULL;
    return true;
}
void listcreate(list2 &first,int x)//链表插入新元素
{
    list2 p=first,r;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    r=new list1;
    r->data=x;
    p->next=r;
    r->next=NULL;
}
void listinsert(list2 &first,int n,int x)//在固定位置插入元素
{
    list2 p=first,r;
    int i=1;
    while(i<n)
    {
        p=p->next;
        i++;
    }
    r=new list1;
    r->data=x;
    r->next=p->next;
    p->next=r;
}
int getlist(list2 &first,int n)//找到第n个节点的数据
{
    int i=0;
    list2 p=first;
    while(i<n)
    {
        p=p->next;
        i++;
    }
    return p->data;
}
int findlist(list2 &first,int x)//找到第几个节点的数据是x
{
    int i=1;
    list2 p=first->next;
    while(p!=NULL)
    {
        if(p->data==x)
            return i;
        else
        {
            p=p->next;
            i++;
        }

    }
}
void deletelist(list2 &first,int n)//删除链表的第几个节点
{
    int i=1;
    list2 r=first,p=first->next;
    while(i<n)
    {
        p=p->next;
        r=r->next;
        i++;
    }
    r->next=p->next;
    free(p);
}
void printlist(list2 &first)//遍历链表并输出数据
{
    list2 p=first->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
int main()
{
    list2 first;
    initlist(first);
    int i,x;
    for(i=0;i<5;i++)
    {
        scanf("%d",&x);
        listcreate(first,x);
    }
    x=getlist(first,3);
    printf("%d\n",x);
    x=findlist(first,2);
    printf("%d\n",x);
    listinsert(first,1,6);
    printlist(first);
    deletelist(first,6);
    printlist(first);

    return 0;
}

循环链表

#include <iostream>

using namespace std;
typedef struct node{
    int data;
    struct node *next;
}list1,*list2;
bool initlist(list2 &first)//链表初始化
{
    first=new list1;
    first->next=first;
    return true;
}
void listcreate(list2 &first,int x)//链表插入新元素
{
    list2 p=first,r;
    while(p->next!=first)
    {
        p=p->next;
    }
    r=new list1;
    r->data=x;
    p->next=r;
    r->next=first;
}
void listinsert(list2 &first,int n,int x)//在固定位置插入元素
{
    list2 p=first,r;
    int i=1;
    while(i<n)
    {
        p=p->next;
        i++;
    }
    r=new list1;
    r->data=x;
    r->next=p->next;
    p->next=r;
}
int getlist(list2 &first,int n)//找到第n个节点的数据
{
    int i=0;
    list2 p=first;
    while(i<n)
    {
        p=p->next;
        i++;
    }
    return p->data;
}
int findlist(list2 &first,int x)//找到第几个节点的数据是x
{
    int i=1;
    list2 p=first->next;
    while(p!=first)
    {
        if(p->data==x)
            return i;
        else
        {
            p=p->next;
            i++;
        }

    }
}
void deletelist(list2 &first,int n)//删除链表的第几个节点
{
    int i=1;
    list2 r=first,p=first->next;
    while(i<n)
    {
        p=p->next;
        r=r->next;
        i++;
    }
    r->next=p->next;
    free(p);
}
void printlist(list2 &first)//遍历链表并输出数据
{
    list2 p=first->next;
    while(p!=first)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
int main()
{
    list2 first;
    initlist(first);
    int i,x;
    for(i=0;i<5;i++)
    {
        scanf("%d",&x);
        listcreate(first,x);
    }
    x=getlist(first,3);
    printf("%d\n",x);
    x=findlist(first,2);
    printf("%d\n",x);
    listinsert(first,1,6);
    printlist(first);
    deletelist(first,6);
    printlist(first);
    return 0;
}

就是将单链表的尾节点从指向NULL改成指向first

双向链表

#include <iostream>

using namespace std;
typedef struct node{
    int data;
    struct node *prior;
    struct node *next;
}list1,*list2;
bool initlist(list2 &first)//链表初始化
{
    first=new list1;
    first->prior=NULL;
    first->next=NULL;
    return true;
}
void listcreate(list2 &first,int x)//链表插入新元素
{
    list2 p=first,r;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    r=new list1;
    r->data=x;
    r->prior=p;
    p->next=r;
    r->next=NULL;
}
void listinsert(list2 &first,int n,int x)//在固定位置插入元素
{
    list2 p=first,r;
    int i=1;
    while(i<n)
    {
        p=p->next;
        i++;
    }
    if(p->next!=NULL)
    {
        r=new list1;
        r->data=x;
        r->next=p->next;
        r->prior=p;
        p->next->prior=r;
        p->next=r;
    }
    else
    {
        r=new list1;
        r->data=x;
        r->next=NULL;
        r->prior=p;
        p->next=r;
    }

}
void deletelist(list2 &first,int n)//删除链表的第几个节点
{
    int i=1;
    list2 r=first,p=first->next;
    while(i<n)
    {
        p=p->next;
        r=r->next;
        i++;
    }
    if(p->next!=NULL)
    {   p->next->prior=r;
        r->next=p->next;
        free(p);
    }
    else
    {
        r->next=p->next;
        free(p);
    }
}
void printlist(list2 &first)//遍历链表并输出数据
{
    list2 p=first->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
int main()
{
    list2 first;
    initlist(first);
    int i,x;
    for(i=0;i<5;i++)
    {
        scanf("%d",&x);
        listcreate(first,x);
    }
    listinsert(first,6,6);
    printlist(first);
    deletelist(first,1                                   );
    printlist(first);
    return 0;
}