数据结构课程设计

（三）概要设计。

在做第一题集合运算时，我通过有序单链表实现集合的交运算，并运算，差运算。首先，我要对集合中的元素用有序单链表进行存储。我首先通过直接插入排序对数组进行排序，使数组升序排列（因为我使用尾插法建立有序链表）。

在计算交集时，只需要查找单链表a和单链表b中相同的元素并保留在单链表a中。由于用有序单链表表示集合，所以判断元素是否在b中不需要遍历表b，而是从上次搜索到的位置开始，若搜索过程中，遇到一个其值比该元素大的结点，便可以断定该元素不在该链表中，为此需设两指针p , q分别指向当前被比较的两个结点，会出现以下三种情况：

1若p->data>q->data,说明还未找到，需在表b中继续查找。

2 若p->datadata,说明b中无此值，处理表a中的下一个结点。

3 若p->data==q->data,说明找到了公共元素。

同理，求并运算时，只需对单链表b中的每一个元素x,在单链表a中进行查找，若存在和x不相同的元素，则将该结点插入单链表a中。求差运算时，只需对单链表b中的每个元素x，在单链表a中查找，若存在与x相同的结点，则将该结点从单链表a中删除。

四）详细设计。

#ifndef linklist_h

#define linklist_h

template

struct node

datatype data; node*next; }

template

class linklist

public:

linklist();linklist(datatype a,int n);

~linklist();void printlist();node* first;

#endif

#include

using namespace std;

#include""

template

linklist::linklist()

first=new node; first->next=null; }

template

linklist::linklist(datatype a,int n)

node*r,*s;

first=new node; r=first;

for(int i=0;i

r->next=null;

template

linklist::~linklist()

node*q=null;

while(first!=null)

template

void linklist::printlist()

node *p=first->next;

while(p!=null)

cout<}

template

/要查找单链表a和单链表b中相同的元素并保留在单链表a中。

void jiaoji(node *a,node *b) /交运算。

node *pre,*p,*q;

pre=a;p=a->next;q=b->next;

while(p!=null&&q!=null)

else if(p->data>q->data) q=q->next;else

template

/对单链表b中的每个元素x，在单链表a中查找，若存在与x相同的结点，则将该结点从单链表a中删除。

void chaji(node *a,node *b)//a-b

node *pre, *p, *q;

pre=a;p=a->next; q=b->next;

while(p!=null &&q!=null)

//始终保证p=pre->next;

if(p->data>q->data) q=q->next;

if(p->data==q->data)

pre->next=p->next; delete p; p=pre->next; q=q->next; }

template

/对单链表b中的每一个元素x,在单链表a中进行查找，若存在和x不相同的元素，则将该结点插入单链表a中。

void bingji(node *a,node *b)

node *pre,*p,*q;

node *s=null;

pre=a;p=a->next;q=b->next;

while(p!=null&&q!=null)

else if(p->data==q->data)

void insertsort(char r,int n)

for(int i=1;i

r[j+1]=r[n];

#include

using namespace std;

#include ""

void main()

cout<<"注意，输入的字符串必须为小写字母，且不出现重复字母！"

cout<<"请输入字符串："

linklistl1(r1,k1+1);/尾插法 linklistl2(r2,k2+1);

cout<<"输出："

cout<<"1.交集。">choice;

if(choice>0&&choice<4)

switch(choice)

一）设计题目。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了