1.
（1）顺序存储结构和链式存储结构的优缺点
顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
- 优点：存储空间利用率高。
- 缺点：插入或删除元素时不方便。
链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针.
- 优点：插入或删除元素时很方便，使用灵活。
- 缺点：存储密度小（<1），存储空间利用率低。
（2）使用情况
顺序表适宜于做查找这样的静态操作；
链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
（3）顺序表与链表的比较
-
基于空间的比较
-
存储分配的方式
顺序表的存储空间是静态分配的- 链表的存储空间是动态分配的
- 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
- 顺序表的存储密度 = 1
- 链表的存储密度 < 1
-
基于时间的比较
-
存取方式
顺序表可以随机存取，也可以顺序存取- 链表是顺序存取的
- 插入/删除时移动元素个数
- 顺序表平均需要移动近一半元素
- 链表不需要移动元素，只需要修改指针
2.
顺序表A，长度为n，请设计一个算法，删除表A中所有的值为b的元素？
#include <stdio.h>
int L_Delete (int *A, int n, int b);
int main(){
int A[] = {3,1,2,3,4,5,3,6,7,8,3};
int n=sizeof(A)/sizeof(A[0]);
int num = L_Delete(A,n,3);
for(int i=0;i<num;i++){
printf("%d ",A[i]);
}
return 0;
}
int L_Delete (int *A, int n,int b){ /* A是线性表，n是表长，i是删除位置 */
/* y用于保存将要删除的第i个元素 */
if (n>0){
int i;
for (i=0; i<n; i++){
if(A[i]==b){
int j;
for(j=i;j<n;j++){
A[j] = A[j+1]; /* 移动元素 */
}
n -= 1; /*修正表长 */
//printf("n=%d\n",n);
}
}
}
return n;
} /* 算法结束 */
3.
顺序表A长度为m，顺序表B长度为n，表A和B中的元素均按递增顺序排列，请编写一个算法，将A和B合并为新的序列C 。
#include <stdio.h>
#define N1 sizeof(A)/sizeof(A[0])
#define N2 sizeof(B)/sizeof(B[0])
void L_sort(int *A, int n);
//void L_com(int *A,int *B,int *C,int n);
int main(){
int A[] = {1,3,5,7,9};
int B[] = {2,4,6,8,10};
int n = N1 + N2;
int C[n];
int i;
for(i=0;i<N1;i++){
C[i] = A[i];
printf("%d ",C[i]);
}
for(i=N1;i<n;i++){
C[i] = B[i-N1];
printf("%d ",C[i]);
}
//L_com(A,B,C,n);
L_sort(C,n);
printf("\n");
for(i=0;i<n;i++){
printf("%d ",C[i]);
}
}
void L_sort(int *C,int n){
int i,j;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(C[i]>C[j]){
int k=C[i];
C[i] = C[j];
C[j] = k;
}
}
}
}
4.
线性表A，长度为n，采用链式存储结构，表头指针为H，请设计一个算法，删除链表H中元素值为b的所有结点。
#include <stdlib.h>
#include <stdio.h>
#define N sizeof(A)/sizeof(A[0])
struct node{
int Data;
struct node *Link;
} *H;
struct node *del(struct node *list, int b);
struct node *add_to_list(struct node *list,int b);
void main(){
int A[]={25,73,60,37,98,90,24};
int i;
printf("数组中元素值作为输入:\n");
for (i=0; i<N; i++){
printf("%5d",A[i]);
}
struct node *first =NULL;
for (i=0; i<N; i++){
first = add_to_list(first,A[i]);
}
printf("\n打印链表中的结点元素:\n");
struct node *p = first;
while (first!=0) {printf("%5d",first->Data); first=first->Link;}
int flag = 37;
struct node *q = del(p,flag);
printf("\n打印删除%3d结点后的链表元素:\n",i);
while (q!=0) {printf("%5d",q->Data); q=q->Link;}
printf("\n");
}
struct node *add_to_list(struct node *list,int b){
struct node *new_node;
new_node = malloc(sizeof(struct node));
if(new_node == NULL){
printf("Error!");
exit(EXIT_FAILURE);
}
new_node->Data = b;
new_node->Link = list;
return new_node;
}
struct node *del(struct node *list, int b){
struct node *cur,*prev;
for(cur=list,prev=NULL;cur!=NULL&&cur->Data!=b;prev=cur,cur=cur->Link);
if(cur==NULL) return list;
if(prev==NULL) list = list->Link;
else prev->Link = cur->Link;
free(cur);
return list;
}
5.
线性表A，长度为n，采用链式存储结构，表头指针为H，请设计一个算法，删除链表H中元素值为b的所有结点。
#include<stdio.h>
#include<stdlib.h>
#define N 10
typedef struct node{
int data;
struct node* next;
}ElemSN;
//创建一个单向链表
ElemSN* CreatLink(int a[],int n)
{
ElemSN *head,*tail,*p;
head=NULL;
for(int i=0;i<n;i++)
{
p=(ElemSN*)malloc(sizeof(ElemSN));
p->data=a[i];
p->next=NULL;
if(!head)
{
head=tail=p;
tail->next=NULL;
}
else
{
tail=tail->next=p;
tail->next=NULL;
}
}
return head;
}
//删除重复值
ElemSN* DelSameNode(ElemSN *head)
{
ElemSN *Pkey,*p,*q;
Pkey=head;
while(Pkey)
{
q=Pkey;
p=Pkey->next;
while(p)
{
if(p->data-Pkey->data)
{
q=p;
p=p->next;
}
else
{
q->next=p->next;
p=q->next;
}
}
Pkey=Pkey->next;
}
return head;
}
//打印删除结点后的链表
void PrintLink(ElemSN* head)
{
ElemSN *p=head;
for(;p;p=p->next)
printf("%5d",p->data);
}
int main(void)
{
ElemSN *head;
int a[N]={3,2,3,8,4,3,4,9,2,3};
head=CreatLink(a,N); //创建单向链表，返回头指针
head=DelSameNode(head); //删除链表中数据域值重复的结点
PrintLink(head); //打印删除结点之后的链表
}
网友评论