沈师PTA数据结构第2章实验题集2—链表操作

R7-5 链表倒数n个结点的乘积 (20 分)

本题要求计算单链表倒数n个结点的乘积。例如，给出单链表1 2 3 4 5，则倒数2个结点的乘积为20。

输入格式:

输入有2行，第一个行为2个非负整数m和n。其中m为链表结点个数，n为链表倒数结点的数量。题目保证计算结果在int范围内。 第二行为链表的m个数，以空格分隔。

输出格式:

在一行中输出倒数n个结点的乘积。

输入样例:

5 2
1 2 3 4 5
结尾无空行

输出样例:

20
结尾无空行

样例解释：

20 = 4 * 5

#include
#include
 
typedef struct node{
	int data;
	struct node *next;
}LinkListNode;

LinkListNode* CreateList(int a[],int m){
	LinkListNode *node,*head,*p;
	int i;
	head = (LinkListNode*)malloc(sizeof(LinkListNode));
	p = head;
	
    for(i = 0;idata = a[i];
		p->next = node;
		p = node;
	}
	p->next = NULL;
	return head;
} 

int main(){
	int m,n;//m为链表结点个数，n为链表倒数结点的数量
	int i;
	scanf("%d %d",&m,&n);
	int a[m];
	for(i = 0;inext;
	int local = m-n;
	if(local == m){
		printf("0");
		return 0;
	}
	for(i = 0;i < local;i++){
		p = p->next;
	}
 
	int result = 1;
	for(i = 0;idata;
		if(p->next == NULL){
			break;
		}
		p = p->next;
	}
	printf("%d\n",result);
	return 0;
}

R7-6 在有序链表中插入数据 (20 分)

给定一批严格递增排列的整型数据，给定一个x，若x不存在，则插入x，要求插入后保持有序。存在则无需任何操作。

输入格式:

输入有两行： 第一个数是n值，表示链表中有n个数据。后面有n个数，分别代表n个数据。 第二行是要插入的数。

输出格式:

输出插入后的链表数据，以空格分开。行末不能有多余的空格。

输入样例1:

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

5 1 3 6 9 11
4
结尾无空行

输出样例1:

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

1 3 4 6 9 11
结尾无空行

输入样例2:

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

5 1 3 6 9 11
3
结尾无空行

输出样例2:

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

1 3 6 9 11
结尾无空行

#include
using namespace std;

template 
struct Node{
    DataType data;               //数据域
    Node *next;       //指针域
};

template 
class LinkList{
public:
    LinkList();                      //无参构造函数，建立只有头结点的空链表
    LinkList(DataType a[], int n);       //有参构造函数，建立有n个元素的单链表
    ~LinkList();                     //析构函数
    int Length();                     //求单链表的长度
    void Insert(DataType x);       //插入操作，第i个位置插入值为x的结点
    void PrintList( );                  //遍历操作，按序号依次输出各元素
private:
    Node *first;           //单链表的头指针
};

template 
LinkList :: LinkList( ){
    first = new Node;              //生成头结点
    first->next = nullptr;                      //头结点的指针域置空
}

template 
LinkList :: ~LinkList( ){
    Node *q = NULL;
    while (first != NULL){        //释放单链表的每一个结点的存储空间
        q = first;                 //暂存被释放结点
        first = first->next;         // first指向被释放结点的下一个结点
        delete q;
    }
}
template 
void LinkList :: PrintList( ){
    int flag=0;
    Node *p = first->next;                //工作指针p初始化
    while (p!= nullptr){
        if(flag==0){
            cout << p->data;
            flag=1;
        }else{
            cout << " "<< p->data ;
        }
        p = p->next;                 //工作指针p后移，注意不能写作p++
    }
    cout<
void LinkList :: Insert(DataType x){
    Node *Z = new Node;
    Z->data = x;
    Node *p = first, *s = first->next;
    //工作指针p指向要插入的前一个结点
    //s为p之后的一个结点，判断是否与要插入的值相等
    
    if (p->next == NULL)//链表为空链表
    {//要插入的元素放在开头
        Z->next = NULL;
        p->next = Z;
        p = Z;
        return;
    }
    
    while (s->data data&&s->next!=nullptr){//查找第i – 1个结点
        p = p->next;
        s=s->next;
    }

    if(s->data == Z->data){//元素已存在
        delete Z;//删除要插入的结点
        return;
    }    
    if(s->data>Z->data){
    Z->next = p->next; //将结点Z插入到结点p之后
    p->next = Z;
    return;
    }
    if(s->next==nullptr){//找到链表结尾了，也找不到第i-1个结点
        s->next=Z;//将结点插在最后
        Z->next=nullptr;
        return;
    }
}

template 
LinkList :: LinkList(DataType a[ ], int n){
    first = new Node;                    //生成头结点
    Node *r = first, *s = nullptr;           //尾指针初始化
    for (int i = 0; i < n; i++){
        s = new Node;
        s->data = a[i];
        r->next = s;
        r = s;                 //将结点s插入到终端结点之后
    }
    r->next = nullptr;        //单链表建立完毕，将终端结点的指针域置空
}


int main( ){
    int a[10000];
    int i,n;
    cin>>n;
    for(i=0;i>a[i];
    }
    LinkList L(a,n);
    int b;
    cin>>b;
    L.Insert(b);
    L.PrintList();
    return 0;
}