Ⅰ 求C语言描述的,用线性表的,求交集的算法
先排序两个先行表，然后去除重复项。
从一个表(a)第一项开始，为关键字扫描另一个表(b)，找一个与其相等的，如果找到，那么在b表之前的项也不会是a表中的项了，然后从a表下一项作关键字，从b表被匹配的元素的下一项开始继续搜索，如果没有找到与a中第一项相等的，到遇到比该项大的项时，便从a中下一项开始，重复以上步骤。
排序就不说了，好多种，冒泡，快排，插入，二分插入都行。去除重复项，可以用以下算法
void StripRepeatElement(int Array[],int Arraylen)
{
int Count = 0;//重复计数器
int i;
for(i = 0;i < ArrayLen;i++)
{
if(Array[i] == Array[i + 1])
{
Count++;
}
else
{
Array[i - Count] = Array[i];
}
}
}
复杂度为O(n)
以下为求交集的算法，假设两个表都已经排过序和剔出重复项了
void GetIntersection(int A[],int Alen,int B[],int Blen)
{
int i = 0,j = 0;
while(i < Alen)
{
while(j < Blen)
{
if(A[i] == B[j])
{
//交集
printf(" %d ",A[i]);
j++;
break;
}
else if(A[i] < B[j])
{
//从A的下一项开始匹配
break;
}
else
{
//比较B的下一项
j++;
}
}
i++;
}
}
复杂度也为O(n)
Ⅱ 求大神帮忙用C语言写一个程序。 要求：定义两个线性表（内容由用户输入），合并这两个线性表，并按顺序
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include <stdbool.h>
typedef struct{
int *data;
int length; // 线性表的长度
int top; // 线性表的当前元素个数
}List;
// 初始化线性表
void list_init(List *li,int length){
li->length = length;
li->top = 0;
li->data = (int*) malloc(li->length * sizeof(int));
}
// 向线性表插入元素
bool add_list(List* li, int data){
if(li->top >= li->length){
return false;
}
li->data[li->top++] = data;
return false;
}
// 将两个线性表合并并对元素进行排序
void merge_list(List *dest, List *li1, List *li2){
list_init(dest, li1->top+li2->top+1);
// 把线性表li1,li2的所有元素添加到线性表dest中
int i = 0;
while(i < li1->top){
add_list(dest, li1->data[i]);
i++;
}
i = 0;
while(i < li2->top){
add_list(dest, li2->data[i]);
i++;
}
// 把线性表dest元素进行排序(由大到小)
for(i=0; i<dest->top; i++){
int j;
for(j=i; j<dest->top; j++){
if(dest->data[i] < dest->data[j]){
int t = dest->data[i];
dest->data[i] = dest->data[j];
dest->data[j] = t;
}
}
}
}
// 显示线性表
void show_list(List *li){
int i;
for(i=0; i<li->top; i++){
printf("%3d",li->data[i]);
if((i+1)%10 == 0){
printf("\n");
}
}
printf("\n");
}
int main(void)
{
int arr1[7]={11,4,7,2,9,15,10};
int arr2[5]={2,1,5,1,19};
List li1;
list_init(&li1, 50);
int i;
for(i=0; i<7; i++){
add_list(&li1,arr1[i]);
}
show_list(&li1);
List li2;
list_init(&li2, 50);
for(i=0; i<5; i++){
add_list(&li2,arr2[i]);
}
show_list(&li2);
List dest;
merge_list(&dest, &li1, &li2);
show_list(&dest);
return 0;
}
Ⅲ 帮用C语言弄两个线性表 谢了 挺简单的
#include <stdio.h>
#include <stdlib.h>
typedef struct _Lnk
{
int num;
struct _Lnk * next;
}LNK, * PLnk;
int * MallocMem(int num);
void InitLnk(PLnk pHead);
void InitArr(int * pArr, int num);
PLnk GetNiLnk(PLnk lnk);
int * GetNiArr(int * arr, int num);
void ShowLnk(char * pstr, PLnk lnk);
void ShowArr(char * pstr, int * arr, int num);
int main(void)
{
// 初始化原始的链表
PLnk pHead = (PLnk)malloc(sizeof(LNK));
printf("现在开始输入链表数据\n");
InitLnk(pHead);
// 初始化原始的顺序表
int num=0;
char tmp;
while ((tmp=getchar())!='\n')
{
continue;
}
printf("请输入元素的个数:\n");
scanf("%d", &num);
//printf("指定的元素个数为：%d\n", num);
int * pArr = NULL;
int * pNiArr = NULL;
if (num>0)
{
pArr = MallocMem(num);
InitArr(pArr, num);
}
PLnk pNiLnk = GetNiLnk(pHead);
if (pArr != NULL)
{
pNiArr = GetNiArr(pArr, num);
}
ShowArr("原始顺序表：", pArr, num);
if (pNiArr != NULL)
{
ShowArr("倒置顺序表：", pNiArr, num);
}
ShowLnk("原始链表：", pHead);
ShowLnk("倒置链表：", pNiLnk);
return 0;
}
// subfunctions:
int * MallocMem(int num)
{// 为顺序表分配内存
int * pArr = (int *)malloc(sizeof(num));
return pArr;
}
void InitLnk(PLnk pHead)
{// 初始化链表的值
int tmp = 0;
printf("请输入数据：(ctrl+x 结束输入)\n");
while (scanf("%d", &tmp))
{
PLnk newnode = (PLnk)malloc(sizeof(LNK));
newnode->num = tmp;
pHead->next = newnode;
pHead = newnode;
}
pHead->next = NULL;
return;
}
void InitArr(int * pArr, int num)
{// 初始化顺序表的值
for(int i=0; i<num; i++)
{
printf("第 %d 数值= ", i+1);
scanf("%d", &pArr[i]);
}
return;
}
PLnk GetNiLnk(PLnk lnk)
{// 获得链表的倒序
PLnk pNi = (PLnk)malloc(sizeof(LNK));
pNi->next = NULL;
PLnk pHead = pNi, pTmp;
while (lnk = lnk->next)
{
pHead->num = lnk->num;
pTmp = pHead;
pHead = (PLnk)malloc(sizeof(LNK));
pHead->next = pTmp;
}
return pHead;
}
int * GetNiArr(int * arr, int num)
{// 获取顺序表的倒序
int * pNi = MallocMem(num);
for (int i=0; i<num; i++)
{
pNi[i] = arr[num-i-1];
}
return pNi;
}
void ShowLnk(char * pstr, PLnk lnk)
{// 显示链表信息
printf("%s\n", pstr);
int i=0;
while (lnk = lnk->next)
{
printf("%d ", lnk->num);
if ((++i)%5==0)
{
printf("\n");
}
}
printf("\n");
return ;
}
void ShowArr(char * pstr, int * arr, int num)
{// 显示顺序表信息
printf("%s\n", pstr);
for (int i=0; i<num; i++)
{
printf("%d ", arr[i]);
if ((i+1)%5==0)
{
printf("\n");
}
}
printf("\n");
return ;
}
在一个程序里面了
自己运行了下应该没什么问题
但是没有做内存的释放等操作， 只是简单的实现了你说的两个功能
Ⅳ C语言线性表基本操作求助
#include<stdio.h>
#include<stdlib.h>
# define MAXSIZE 100
# define OK 1
# define ERROR 0
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;
}Sqlist;
int CreateList(Sqlist *L)//创建线性表
{
int i, n, num;
printf("请输入元素个数：");
scanf("%d", &n);
printf("请依次输入整数值：");
for (i = 1; i <=n; i++)//一共n个元素,=号
{
scanf("%d", &num);
L->data[i] = num;
L->length++;//长度加1
}
return OK;
}
int ListLength(Sqlist* L)//返回线性表长度
{
printf("线性表的长度为：%d", L->length);
return L->length;
}
int PrintList(Sqlist* L)//依次输出线性表
{
int i;
for (i = 1; i <= L->length; i++)
{
printf("%d\t", L->data[i]);
}
printf("\n");
return OK;
}
int InsertList(Sqlist *L, int i, ElemType e)//插入元素s
{
int k;
if (L->length == MAXSIZE )
return ERROR;
if (i<1 || i>L->length +1 )
return ERROR;
if (i <= L->length)
{
for (k = L->length; k >= i - 1; k--)//k--，下标从1开始则lengh位置已有元素，不应length-1
L->data[k + 1] = L->data[k];
}
L->data[i] = e;//i不减1
L->length++;
return OK;
}
int DeletList(Sqlist *L, int i)//删除元素
{
int k;
if (L->length == 0)//==
return ERROR;
if (i<1 || i>L->length)
return ERROR;
if (i <= L->length)
{
for (k = i; k < L->length; k++)
L->data[k] = L->data[k+1];//应该这样
}
L->length--;
return OK;
}
int GetElem(Sqlist* L, int i, ElemType* e)//用e返回线性表中第i个元素的值
{
if (L->length ==0 || i<1 || i>L->length)//==
return ERROR;
*e = L->data[i];//前面下标都是1开始，就不用-1了
return OK;
}
int MergeList(Sqlist* L1, Sqlist* L2, Sqlist *L3)//两个线性表求并集，结果放在L3里
{
int i, j, k;
i = 1;
j = 1;
k = 1;
while ((i <= L1->length) && (j <= L2->length))
{
if (L1->data[i] == L2->data[j])
{
L3->data[k] = L1->data[i];
i++;
j++;
}
else
if (L1->data[i] < L2->data[j])
{
L3->data[k] = L1->data[i];
i++;
}
else
{
L3->data[k] = L2->data[j];
j++;
}
k++;
}
if (i > L1->length)
for (i = j; i <= L2->length; i++)
{
L3->data[k] = L2->data[i];
k++;
}
else
for (j = i; j <= L1->length; j++)
{
L3->data[k] = L1->data[j];
k++;
}
L3->length = k - 1;
return OK;
}
void menu()
{
printf("\n");
printf(" *******************顺序线性表功能菜单*******************\n");
printf(" * 1：建立线性表 2：插入元素 *\n");
printf(" * 3: 删除元素 4：合并线性表 *\n");
printf(" * 5：打印线性表 6：查找特定元素 *\n");
printf(" * 7：线性表长度 8：退出 *\n");
printf(" ********************************************************\n");
printf(" 请输入你的选择：");
}
void main()
{
Sqlist L, L1, L2, L3;
ElemType e;
int i,n,flag;
char a;
L.length = 0;
//int CreateList(Sqlist *L);//函数原型
//int ListLength(Sqlist* L);
//int PrintList(Sqlist* L);
//int InsertList(Sqlist *L, int i, ElemType e);
//int DeletList(Sqlist *L, int i);
//int GetElem(Sqlist* L, int i, ElemType e);
//int MergeList(Sqlist L1, Sqlist L2, Sqlist *L3);
menu();
do
{
scanf("%d",&n);
if(n>=1&&n<=7)
{
flag=1;
break;
}
else
{
flag=0;
printf("您输入有误，请重新选择!");
}
}
while(flag==0);
while(flag==1)
{
switch (n)
{
case 1:
CreateList(&L);
PrintList(&L);
break;
case 2:
printf(" 请输入要插入的数据元素：");
scanf("%d", &e);
printf(" 请输入要插入的元素位置：");
scanf("%d", &i);
InsertList(&L, i, e);
break;
case 3:
printf(" 请输入要删除的元素位置：");
scanf("%d", &i);
DeletList(&L, i);
PrintList(&L);
break;
case 4:
printf(" 创建第一个顺序表");
CreateList(&L1);
printf(" 创建第二个顺序表");
CreateList(&L2);
PrintList(&L1);
PrintList(&L2);
MergeList(&L1, &L2, &L3);
PrintList(&L3);
break;
case 5:
PrintList(&L);break;//这里开始都忘了break
case 6:
printf("请输入查看元素序号：");
scanf("%d", &i);
GetElem(&L, i, &e);
printf("第%d个元素为%d", i, e);break;
case 7:
ListLength(&L);break;
case 8:
exit(0);
break;
default:
break;
}
getchar();
printf("\n");
printf("是否继续进行(y or n):\n");
scanf("%c",&a);
if(a=='y')
{
flag=1;
system("cls"); /*清屏*/
menu(); /*调用菜单函数*/
printf("请再次选择你需要操作的步骤(1--7):\n");
scanf("%d",&n);
printf("\n");
}
else
exit(0);
}
}