Respuestas completas al conjunto de preguntas sobre estructura de datos de Yan Weimin de la Universidad de Tsinghua (versión en lenguaje C)
Introducción al Capítulo 1
1.16
void print_descending(int x, int y, int z)// Genera tres números en orden de mayor a menor
{
scanf("%d,%d,%d",&x,&y,&z); y; //<-> es un operador binario que indica intercambio, igual que a continuación
if(y
if(x< y) x<->y; //ordenación de burbujas
printf("%d %d %d",x,y,z
}//print_descending
);1.17
Estado fib(int k,int m,int &f)//Encuentra el valor f del elemento m-ésimo de la secuencia de Fibonacci de orden k
{
int tempd;
if(k<2||m<0) devuelve ERROR;
if(m si no (m==k-1) f=1; si no { for(i=0; i<=k-2;i++) temp[i]=0; temp[k-1]=1 //Inicialización for(i=k;i <; =m;i++) //Encuentra el valor del késimo al mésimo elemento de la secuencia { sum=0 for(j= i-k; ;j temp[i]=suma } f=temp[m] ; } return OK; }//fib Análisis: al guardar los resultados calculados, este método La complejidad del tiempo es solo O (m ^ 2) Si se usa programación recursiva (la mayoría de la gente pensará primero en métodos recursivos), la complejidad del tiempo será tan alta como O (k ^ m). > p> typedef struct{ char *sport; enum{masculino, femenino} género; char nombre de la escuela; //nombre de la escuela' A','B','C','D'o'E' char *resultado int puntuación } tipo de resultado; /p> typedef struct{ int puntuación masculina; int puntuación femenina; int puntuación total } tipo de puntuación; /p> resumen vacío (resultado tipo resultado[ ])//Encuentre los puntajes totales de hombres y mujeres y el puntaje total del equipo de cada escuela, suponiendo que los resultados se hayan almacenado en la matriz de resultados[ ] { puntuación de tipo de puntuación i=0 mientras(resultado[i].sport!=NULL) cambiar(resultado[i].nombredelaescuela) { caso 'A': puntuación[ 0 ]. puntuación total+=resultado[ i].puntuación; if(resultado[i].gender==0) puntuación[ 0 ].malescore+=resultado[i].score else puntuación[ 0 ] .femalescore+=resultado[i].score; descanso; caso 'B': puntuación .totalscore+=resultado[i].score; /p> if(resultado[i].gender==0) puntuación .malescore+=result[i].score else puntuación .femalescore+=result[i].score; p> p> romper ……………… } i++; for(i=0;i<5;i++) { printf("Escuela %d:\n",i printf("Puntuación total de hombres:%d\n",score[i].malescore printf("Puntuación total de mujeres:%d\n",score[ i].femalescore) ; printf("Puntuación total de todos:%d\n\n",score[i].totalscore }
1.19
Estado algo119(int a[ARRSIZE])//Encuentra el valor de la secuencia i!*2^i y no exceda maxint
{
último=1
for(i=1;i<=ARRSIZE;i++)
{
a[i-1 ]=último*2*i;
if((a[i-1]/último)!=(2*i)) reurn OVERFLOW; p>last=a[i -1];
return OK;
}
}//algo119
Análisis: Cuándo el resultado de un determinado elemento excede Cuando se usa maxint, se producirá una excepción cuando se divida por el cociente del elemento anterior
1.20
void polyvalue()
{
anuncio flotante ;
float *p=a;
printf("Ingrese el número de términos:");
scanf("%d",&n);
printf("Ingrese los coeficientes %d de a0 a%d:\n",n,n
printf("Valor de entrada de x:"); ("%f",&x);
p=a;xp=1;sum=0; //xp se usa para almacenar la i-ésima potencia de x
for (i=0;i<=n;i++)
{
suma+=xp*(*p++); p>
}
printf("El valor es:%f",suma);
}//polyvalue
Capítulo 2 Lineal
Tabla
2.10
Estado DeleteK(SqList &a,int i,int k)//Eliminar k elementos a partir del i-ésimo elemento en la tabla lineal a
{
if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
for(count=1;i+count -1<=a.length-k;count++) //Presta atención a las condiciones para el final del ciclo
a.elem[i+count-1]=a.elem[i+count +k-1];
a.length-=k;
return OK;
}//DeleteK
2.11
Estado Insert_SqList(SqList &va,int x)//Inserte x en la lista ordenada creciente va
{
if(va.length+1>va. tamaño de lista) devuelve ERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return OK;
}//Insert_SqList
2.12
int ListComp(SqList A, SqList B)//Compare las tablas de caracteres A y B, y use el valor de retorno para expresa el resultado. Si el valor es positivo, significa A>B; si el valor es negativo, significa A { for(i=1;A.elem[i]|| B.elem[i];i++) if(A.elem[i]!=B.elem[i] ) devolver A.elem[i]-B.elem[i]; devolver 0; }//ListComp 2.13 LNode* Locate(LinkList L,int x)//Elementos en la lista enlazada Buscar, puntero de retorno { for(p=l->next;p&&p-> data!=x;p=p->next); return p; }//Ubicar 2.14 int Longitud (LinkList L) // Encuentra la longitud de la lista vinculada { for(k=0,p=L;p->next;p=p->next ,k++); return k; } //Longitud 2.15 void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//Conecta la lista enlazada hb después de ha para formar la lista enlazada hc { hc=ha;p=ha; while(p ->siguiente) p=p->siguiente; p->siguiente=hb }//ListConcat 2.16
2.17
Inserción de estado (Lista de enlaces &
;L,int i,int b)//Inserte el elemento b antes del i-ésimo elemento de la lista enlazada del nodo sin cabeza L
{
p=L;q=(LinkList *)malloc(sizeof(LNode));
q.data=b;
if(i==1)
{
q.next=p;L=q; //Insertar al principio de la lista enlazada
}
else
{
while(--i>1) p=p->next;
q->next=p->next;p->next=q //Insertar en la posición del i-ésimo elemento
}
}//Insertar
2.18
Estado Eliminar(LinkList &L,int i)//En la lista enlazada de nodos sin cabeza Eliminar el i-ésimo elemento en L
{
if(i==1) L=L->next //Eliminar el primer elemento
else
{
p=L;
while(--i>1) p=p->siguiente;
p ->next=p->next->next; //Eliminar el elemento i-ésimo
}
}//Eliminar
2.19
Estado Delete_Between(Linklist &L,int mink,int maxk)//Eliminar todos los elementos de la lista enlazada L cuyos elementos están ordenados en orden ascendente con valores mayores que mink y menores que maxk
{
p =L;
while(p->next->data<=mink) p=p->next; //p es el último elemento que no sea mayor que mink
if( p->next) //Si hay elementos mayores que mink
{
q=p- >next;
while(q-> data
p->next =q;
}
}//Delete_Between
2.20
Estado Delete_Equal(Linklist &L)//Eliminar todos los elementos con el mismo valor en la lista enlazada L en la que los elementos están ordenados en orden ascendente
{
p=L->next;q=p->next; apunta a dos elementos adyacentes
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p-> next; //Cuando dos elementos adyacentes no son iguales, pyq retroceden un paso
}
else
{
while(q->data==p->data)
{
libre(q);
q=q->siguiente;
}
p->siguiente=q;p=q;q= p->siguiente; //
Eliminar elementos redundantes cuando los elementos adyacentes sean iguales
}//else
}// while
}//Delete_Equal
2.21
void reverse(SqList &A)//Inversión in situ de la lista de secuencia
{
for(i=1,j=A.length;i < j;i++,j--)
A.elem[i]<->A.elem[j];
}//reverse
2.22
void LinkList_reverse(Linklist &L)// Inversión in situ de la lista vinculada para simplificar el algoritmo, suponga que la longitud de la tabla es mayor que 2
{
p=L ->siguiente;q=p->siguiente;s=q->siguiente;p->siguiente=NULL;
while(s->siguiente)
{
q->next=p;p=q;
q=s;s=s->next; //Inserta los elementos de L en la nueva tabla. encabezado uno por uno
}
q->next=p;s->next=q;L->next=s;
}// LinkList_reverse
Análisis: la idea de este algoritmo es insertar el elemento actual q de L en el encabezado de la nueva lista vinculada uno por uno, y p es el encabezado de la nueva lista
2.23
void merge1(LinkList &A, LinkList &B, LinkList &C)//Fusiona las listas enlazadas A y B en C, organiza los elementos de A y B a intervalos y usa el original espacio de almacenamiento
{
p=A-> next;q=B->next;C=A;
while(p&&q)
{
s=p->next;p->next =q; //Inserta los elementos de B
if(s)
{
t=q->next;q->next=s; //Si A no está vacío, inserta los elementos de A
}
p=s;q=t;
}//mientras
}//merge1
2.24
void reverse_merge(LinkList &A ,LinkList &B,LinkList &C)//Fusiona las listas vinculadas A y B con elementos en orden ascendente en C, y Los elementos en C se organizan en orden descendente, utilizando el espacio original
{
pa=A->next;pb=B->next;pre=NULL; //pa y pb apuntan a A respectivamente, el elemento actual de B
while(pa||pb )
{
if(pa->datos
{
pc=pa ;q=pa->next;pa->next=pre;pa=q; //Inserta los elementos de A en la nueva tabla
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; / /Inserta los elementos de B en la nueva tabla
> }
pre=p
c;
}
C=A;A->next=pc; //Construir un nuevo encabezado
}//reverse_merge
Análisis: La idea de este algoritmo es insertar los elementos de A y B en el PC principal de la nueva tabla en orden de pequeño a grande, y finalmente procesar los elementos restantes de A o B.
2.25
void SqList_Intersect(SqList A, SqList B, SqList &C)//Encuentra la intersección de los elementos de las listas lineales A y B con elementos en orden ascendente y guárdalos en C
{
i=1;j=1;k=0;
mientras(A.elem[i]&&B.elem[j])
{
si(A.elem[i] si(A.elem[i]>B.elem[j ]) j++; if(A.elem[i]==B.elem[j]) { C.elem[++k ]=A.elem[i] ; //Cuando se encuentra un elemento que existe tanto en A como en B, i++;j++ //Agréguelo a C } }//mientras }//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)// Reelaborar la estructura de la lista enlazada Pregunta anterior { p=A->next;q=B->next; pc=(LNode*) malloc(sizeof(LNode) ); while(p&&q) { if(p->data else if(p->data>q->data) q=q->siguiente; else { s=( LNode*)malloc(sizeof(LNode)); s->datos=p->datos; pc->next=s;pc= s; p=p->siguiente;q=q->siguiente; } }//mientras C =pc; }//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//Encuentra la intersección de los elementos de las listas lineales A y B con elementos en orden ascendente y almacenarlos nuevamente en A { i=1;j=1;k=0; while(A .elem[i]&&B.elem[j] ) { if(A.elem[i] else if(A.elem[i] >B.elem[j]) j++; else if(A.elem[i]!=A.elem[k]) { A.el em[++k]=A.elem[i]; //Cuando se encuentra un elemento que existe tanto en A como en B i++;j++; a En C } }// while while(A.elem[k]) A.elem[k++]=0; }//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//Vuelva a trabajar la pregunta anterior en la estructura de la lista vinculada { p=A->siguiente;q=B->siguiente;pc=A; mientras(p&&q) { if(p->datos else if(p->datos>q->datos) q=q->siguiente; else if(p->datos!=pc->datos) { pc=pc->siguiente; pc ->datos =p->datos; p=p->siguiente;q=q->siguiente; } }//mientras }//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) { i =0;j=0;k=0;m=0; //i indica la posición original del elemento en A, m es la posición movida while(i { if(B.elem[j] else if(B .elem[j]>C.elem[k]) k++; else { igual=B.elem[j] ; //encontré el mismo elemento while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; /j, Mueve k de regreso al nuevo elemento while(i A.elem[m++]=A.elem[ i++]; //Los elementos que deben conservarse se mueven a la nueva posición while(i } }//mientras mientras(i A.elem[m++]=A.elem [i++]; //A Los elementos restantes se almacenan nuevamente. A.length=m; }// SqList_Intersect_Delete Análisis: primero encuentre la mayor cantidad de elementos de B y C, márquelos como iguales y luego A partir de la posición actual en A, todos los elementos que son menores que lo mismo se retienen (se guardan en una nueva posición), los que son iguales se omiten y, cuando son mayores que lo mismo, el se encuentra lo mismo a continuación 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)// Vuelva a trabajar la pregunta anterior en la estructura de la lista vinculada { p=B->siguiente;q=C->siguiente;r=A-siguiente; while(p&&q&&r) { if( p->datos else if(p->datos>q->datos) q=q->siguiente; else { u=p->data; //Determina el elemento u que se eliminará while(r- >next->data if(r->next->data==u) { s=r->siguiente; while(s->datos==u) { t=s;s=s- >next;free(t); //Determina el puntero del primer elemento s mayor que u }// while r-> next=s; //Eliminar r y elementos entre s }//if while(p->data=u) p=p->next; mientras(q- >datos=u) q=q->siguiente; }//else }//mientras }/ /LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//Eliminar el predecesor directo del nodo s en la lista enlazada circular única { p=s; while(p->next->next!=s) p=p->next; //Encontrar el predecesor p del predecesor de s p->next=s; return OK; }//Delete_Pre 2.32 Estado DuLNode_Pre(DuLinkList &L)//Complete el predominio del nodo de lista enlazada circular bidireccional { for(p=L;!p->next->pre;p=p->next) p->siguiente->pre=p; return OK; }//DuLNode_Pre 2.33 Estado LinkList_Divide(Li nkList &L,CiList &A,CiList &B,CiList &C)//Divida los elementos de la lista enlazada única L en tres listas enlazadas circulares según el tipo. CiList es el tipo de lista enlazada circular única con el nodo principal. { s=L->siguiente; A=(CiList*)malloc(sizeof(CiLNode));p=A; B =(CiList*) malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C //Crea el nodo principal mientras(s) { if(isalphabet(s->datos)) { p ->next=s ;p=s; } else if(isdigit(s->data)) { q->siguiente =s;q=s; } else { r->siguiente=s; r=s; } }//mientras p->next=A;q->next=B;r->next=C ; //Completa el bucle Lista enlazada }//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//Envía los valores de los elementos del Lista enlazada XOR de izquierda a derecha { p=L.left;pre=NULL; while(p) { printf(" %d",p->datos); q=XorP(p->LRPtr,pre); pre=p ;p=q; //Cualquier nodo El valor del campo LRPtr se aplica mediante operación XOR con su puntero de nodo izquierdo para obtener su puntero de nodo derecho } }//Print_XorLinkedList 2.35 Estado Insert_XorLinkedList(XorLinkedList &L,int x,int i)//Insertar elemento x antes del i-ésimo elemento de la lista enlazada XOR L { p=L .left;pre=NULL; r=(XorNode*)malloc(sizeof(XorNode)); r->data=x; if (i==1) //Cuando el punto de inserción está en el extremo izquierdo { p->LRPtr=XorP(p.LRPtr,r ); r->LRPtr=p; L.left=r; devolver OK; } j=1 ;q=p->LRPtr; //Cuando el punto de inserción está en el medio while(++j { q=XorP (p->LRPtr,pre); pre=p;p=q; }// while //Insertar entre los dos nodos p y q p> if(!q) return INFEASIBLE; //no puedo exceder la longitud de la tabla p->LRPtr=XorP(XorP(p->LRPtr,q),r); p> q->LRPtr=XorP(XorP(q->LRPtr,p),r); r->LRPtr=XorP(p,q); //Modificar puntero return OK; }//Insert_XorLinkedList 2.36 Estado Delete_XorLinkedList(XorlinkedList &L,int i)//Eliminar XOR vinculado list L El elemento i-ésimo { p=L.left;pre=NULL; if(i==1) //Eliminar el Situación del punto del nudo más a la izquierda { q=p->LRPtr; q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); devolver OK; } j=1;q=p-> LRPtr ; while(++j { q=XorP(p->LRPtr,pre); pre=p;p=q; }// while //Encontrar el nodo q a eliminar if(!q) return INFEASIBLE //no puedo exceder el longitud de la tabla if(L.right==q) //q es el nodo más a la derecha { p->LRPtr=XorP(p- > LRPtr,q); L.right=p;free(q); devolver OK; } r = XorP(q->LRPtr,p); //Cuando q es el nodo medio, p y r son sus nodos izquierdo y derecho respectivamente p->LRPtr=XorP(XorP(p- >LRPtr, q),r); r->LRPtr=XorP(XorP(r->LRPtr,q),p); //Modificar puntero free(q ); return OK; }//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//Presione 1,3,5, ...4,2 orden reorganiza todos los nodos en la lista enlazada circular bidireccional L { p=L.next; while(p ->siguiente!=L&&p->siguiente->siguiente!=L) { p->siguiente=p->siguiente->siguiente; p=p->next; } //En este momento, p apunta al último nodo impar if(p->next==L) p-> next =L->pre->pre; else p->next=l->pre; p=p->next; //En este momento p apunta al último nodo par while(p->pre->pre!=L) { p->next=p->pre->pre; p> p=p->next; } p->next=L; //Se ha ajustado la estructura de la siguiente cadena. de acuerdo con los requisitos de la pregunta En este momento, la cadena previa permanece en el estado original for(p=L;p->next!=L;p=p->next) p-. >next->pre=p; L- >pre=p; //Ajusta la estructura de la cadena previa, igual que el método 2.32 }//OEReform Análisis: La siguiente cadena y la cadena previa solo se pueden ajustar por separado si al mismo tiempo Si realiza ajustes, debe usar la pila para guardar los punteros de los nodos pares; de lo contrario, la estructura de la lista vinculada. se destruirá y los nodos se perderán 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x )//Buscar en una lista enlazada circular bidireccional con campo freq { p=L.siguiente; while(p.data!=x&&p! =L) p=p->siguiente; if(p==L) return NULL; //No encontrado p->freq++;q=p->pre while(q->freq<=p; ->freq) q=q->pre; //Encontrar la posición de inserción if(q!=p->pre) { p ->pre->siguiente=p->siguiente;p->siguiente->pre=p->pre; q-> siguiente->pre=p;p->siguiente=q-> next; q->next=p;p->pre=q; //Ajustar posición } return p; }//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//Ampliar la potencia Valores de polinomios dispersos almacenados secuencialmente { PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) { while(ex suma+=q->coef *xp; q++; } devolver suma; }//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//Encuentra la diferencia P3 del polinomio disperso P1 menos P2 { PolyTerm *p, *q,*r; Create_SqPoly(P3); //Crea un polinomio vacío P3 p=P1.data; q=P2.data;r=P3.data; mientras(p->coef&&q->coef ) { if(p->exp { r->coef=p- >coef; r->exp=p->exp; p++;r++; } si no (p ->exp { r->coef=-q->coef; r->exp=q-> exp; q++;r++; } else { if((p-> coef-q->coef)!=0) //Solo cuando la resta de términos del mismo grado no es cero, debe almacenarse en P3 { r ->coef=p ->coef-q->coef; r->exp=p->exp;r++; }//si p++;q++; }//else }// while while(p->coef) //Procesa los elementos restantes de P1 o P2 { r->coef=p->coef; r->exp=p->exp; p++;r++; } while(q->coef) { r->coef=-q ->coef; r->exp=q->exp; q++;r++; } }// Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//Derivación del polinomio disperso L almacenado en la estructura de lista circular enlazada del nodo principal { p=L- >siguiente; if(!p->data.exp) { L->siguiente= p->next;p=p-> next; //Omitir elementos constantes } while(p!=L) { p->data.coef*=p->data.exp--;//Derivación para cada término p=p->next; } } //QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)// Divide el polinomio disperso L almacenado en la lista circular enlazada en A que contiene solo términos de orden impar y A que contiene solo términos de orden impar B de términos pares { p=L->next; A=( PolyNode*)malloc(tamañode(PolyNode)); B=(PolyNode*)malloc(tamañode(PolyNode)); pa=A;pb=B; > mientras(p!=L) { si(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } más { pb->siguiente=p;pb=p; } p=p->siguiente; }//mientras pa->next=A;pb->next=B; }//Divide_LinkedPoly