数据结构-2

线性表-单链表

【Elemtype为数据类型】

创建

链表结点结构体创建

typedef struct LNode        //创建结点类型
{
	elemtype data;         //结点中包含数据域
	struct LNode *next;    //结点中包含指向下一个结点的指针
}*Linklist                 //将该类型定义为一个链表（常使用指针方式价）

尾插法创建

void create(Linklist &L,int n)
//传址需要创建的表L，以及初始表长n
{
    L=new Lnode;		//为L新分配一个地址
	L->next=NULL;		//将L的next设为空（前两步为初始化）
    Lnode *E=L;			//令新指针指向L指向的头结点
    int i,a;
	Lnode *p;			//定义另一个指向结点的指针p
    for(i=1;i<=n;i++)	
    {
     cin>>a;			//输入数据a
     p=new Lnode;		//令p指向新建结点
     p->data=a;			//将新建结点的数据域赋值为a
     E->next=p;			//令E的next指向p指向的结点
     p->next=NULL;		//p的next指向空
     E=p;				//指针E后移，指向p指向的结点
    }
}

头插法创建

void create(Linklist &L，int n)
//传址需要创建的表L，以及初始表长n
{
	L=new LNode;
	L->next=NULL;
    int i,a;
	struct LNode *p;
    cin>>a;
    for(i=1;a!=-1;i++)
    {
    p=new LNode;
    p->data=a;
    p->next=L->next;
    L->next=p;
    cin>>a;
    }
}

初始化

注：初始化应当在尾插和头插法前使用，或者不使用

bool init(Linklist &L)       //传址创建的链表
{
	L=new LNode;            //新生成一个结点，让头指针指向头结点
	L->next=NULL;          //为统一操作，头结点仅作为首元结点的前驱，数据域不放入数据，且指针域指向空
	return true;           //返回值提示完成初始化
}

取值

单链表的取值需要顺序遍历，耗时较长，故而不适合频繁获取特定位置的值

bool getelem(Linklist &L,int i,elemtype &e)
//传址数据所在的表，并且传值需要取值的元素序号i，将得到的值传给e
{
	int j;
	LNode *p=L->next;               //令p指向首元结点
	for(j=1;j<i&&p!=NULL;j++)       //j作为计数器，确定遍历到的位置，当p指针指向空或j==i时结束循环
	{
		p=p->next;                  //让p指向p的下一个结点，实现p后移
	}                               //结束循环时，j==i，p指向的结点为第i-1个结点
 	if(p==NULL) return false;       //如果p指针指向空，则返回取值失败
	e=p->next->data;                //否则，将p指向结点的下一个结点的数据域赋给e
	return true;                   //返回取值完成
}

查找

单链表的查找同顺序表一样，需要遍历整个表，比较每个数据域和待查找值，若相同则返回其序号，若始终不相同则返回查找失败

bool find(Linklist &L,LNode *&p,elemtype a)
//传址需要查找的表，查找成功时用于指向查找结果的指针p，同时传值需要查找的数据a
{
	int j;
	p=L->next;
	for(j=1;p->next!=NULL;j++)      //j作为计数器，确定遍历到的位置，当p指针指向为空时结束循环
	{
		if(p->data==a) break;       //查找到与数据a相同的数据域，提前退出循环
		p=p->next;                  //p指针继续后移，继续遍历整个链表
	}
	if(p->next==NULL&&p->data!=a)   return false;  
	//如果p指针已经指向尾结点，且尾结点数据域域不等于a，则查找失败
	//p指针直接能够返回需要查找的节点，不需要另外设置返回
	return true;                   //返回查找成功
}

插入

插入时，需要先让新结点连接需要插入位置前驱的后一个结点，再让前驱的next指针指向新结点，否则会直接丢失后面数据的地址

bool insert(Linklist &L,int i，elem e)
//传址链表，需要插入的位置i，需要插入的元素值e
{
	int j;
	Lnode *p=L->next;                //使p指针指向首元结点
	Lnode *s=new Lnode;              //新建一个结点，并用s指针指向它
	s->data=e;                       //将新建结点的数据域赋为e
	for(j=0;j<i-1&&p!=NULL;j++)      
	//当j移动到需要插入位置的前驱时或者链表结束时结束循环
	{
		p=p->next;                   //让p指向下一个结点
	}
	if(p==NULL) return false;        //如果p指向不合法位置则返回插入失败
	s->next=p->next;                 //否则让s的next指针指向p的下一个结点
	p->next=s;                       //并让p的next指针指向s
	return true;                     //返回成功插入
}

删除

bool del(Linklist &L,int i)
{
	int j;
	Lnode *p=L->next;                //使p指向首元结点
	for(j=0;j<i-1&&p!=NULL)           
	//当j移动到需要删除位置的前驱或链表结束时结束循环
	{
		p=p->next;                  //让p指向p的下一个结点
	}
	if(p=NULL) return false;        //p指向不合法位置时，返回删除失败
	p->next=p->next->next;          //让p的next指针等于p下一个结点的next
	return true;                    //返回删除成功
}

实际题目

R7-3 单链表的创建及遍历 (20 分)

读入n值及n个整数，建立单链表并遍历输出。

输入格式:
读入n及n个整数。

输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。

输入样例:
在这里给出一组输入。例如：

2
10 5

输出样例:
在这里给出相应的输出。例如：

10 5

解法：

#include<iostream>
using namespace std;

typedef struct Lnode
{
    int data;
    struct Lnode *next;
}*Linklist;

void create(Linklist &L,int n)
{
    L=new Lnode;
	L->next=NULL;
    if(n>0) 
    {
        Lnode *E=L;
        int i,a;
	    struct Lnode *p;
        cin>>a;
        for(i=1;i<=n;i++)
        {
        p=new Lnode;
        p->data=a;
        E->next=p;
        p->next=NULL;
        E=p;
        cin>>a;
        }
    }
}

int putout(Linklist &L)
{
    int i;
        struct Lnode *p=L;
        if(L->next==NULL) return 0;
    for(i=0;p->next->next!=NULL;i++)
    {
        cout<<p->next->data<<" ";
        p=p->next;
    }
    cout<<p->next->data;
    return 0;
}

int main()
{
    Linklist list;
    int n;
    cin>>n;
    create(list,n);
    putout(list);
    return 0;
}

R7-1 两个有序链表序列的合并 (20 分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

解法：

#include<iostream>
using namespace std;

typedef struct Lnode
{
    int data;
    struct Lnode* next;
}*Linklist;

bool init(Linklist &L)
{
    L=new Lnode;
    L->next=NULL;
    return true;
}


void create(Linklist &L)
{
    L=new Lnode;
	L->next=NULL;
        Lnode *E=L;
        int i,a;
	    struct Lnode *p;
        cin>>a;
        for(i=1;a!=-1;i++)
        {
        p=new Lnode;
        p->data=a;
        E->next=p;
        p->next=NULL;
        E=p;
        cin>>a;
        }
}


bool addit(Linklist &l1,Linklist &l2,Linklist &l3)
{
    struct Lnode *p1=l1->next,*p2=l2->next, *p3;
    l3=l1;
    p3=l3;
    while(p1&&p2)
    {
	        if(p1->data<=p2->data)
	        {
	        	p3->next=p1;
	        	p3=p1;
	        	p1=p1->next;
	        }
	        else {
	            p3->next=p2;
	            p3=p2;
	        	p2=p2->next;
	        }
    }
    p3->next=p1?p1:p2;
    return true;
}

int putout(Linklist &L)
{
    int i;
        struct Lnode *p=L;
                if(L->next==NULL) {
		cout<<"NULL"; return 0;}
    for(i=0;p->next->next!=NULL;i++)
    {
        cout<<p->next->data<<" ";
        p=p->next;
    }
    cout<<p->next->data;
    return 0;
}

int main()
{
    Linklist L1,L2,L3;
	create(L1);
	create(L2);
	init(L3);
    addit(L1,L2,L3);
    putout(L3);
    return 0;
}

R7-2 两个有序链表序列的交集 (20 分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 2 5 -1
2 4 5 8 10 -1

输出样例:

2 5

解法：

#include<iostream>
using namespace std;

typedef struct Lnode
{
    int data;
    struct Lnode* next;
}*Linklist;

bool init(Linklist &L)
{
    L=new Lnode;
    L->next=NULL;
    return true;
}


void create(Linklist &L)
{
    L=new Lnode;
	L->next=NULL;
        Lnode *E=L;
        int i,a;
	    struct Lnode *p;
        cin>>a;
        for(i=1;a!=-1;i++)
        {
        p=new Lnode;
        p->data=a;
        E->next=p;
        p->next=NULL;
        E=p;
        cin>>a;
        }
}

bool find(Linklist &L,int a)
{
    int j;
    struct Lnode *p;
    p=L->next;
    for(j=1;p->next!=NULL;j++)      
    {
        if(p->data==a) break;       
        p=p->next;                 
    }
    if(p->next==NULL&&p->data!=a)   return false;              
    return true;  
}

bool cutit(Linklist &l1,Linklist &l2,Linklist &l3)
{
    struct Lnode *p1=l1->next,*p2=l2->next,*p3=l3;
    while(p1&&p2)
    {
    	if(p1->data<p2->data)
    	{
    		p1=p1->next;
		}
		else
		if(p1->data==p2->data)
		{
			p3->next=p1;
			p3=p3->next;
			p1=p1->next;
			p2=p2->next;
			
		}
		else
		if(p1->data>p2->data)
		{
			p2=p2->next;
		}
    }
    if(p3->next!=NULL) p3->next=NULL;
    return true;
}

int putout(Linklist &L)
{
    int i;
        struct Lnode *p=L;
        if(L->next==NULL) {
		cout<<"NULL"; return 0;}
    for(i=0;p->next->next!=NULL;i++)
    {
        cout<<p->next->data<<" ";
        p=p->next;
    }
    cout<<p->next->data;
    return 0;
}

int main()
{
    Linklist L1,L2,L3;
	create(L1);
	create(L2);
	init(L3);
    cutit(L1,L2,L3);
    putout(L3);
    return 0;
}